AOJ 0537 Bingo

解説

言い換えると
$1 \leq a_1 < a_2 < \ldots < a_n \leq M $
$a_1 + a_2 + \ldots + a_n = S$
をみたす $a_n$ の作り方を求める問題で,O(NMS) の解法はすぐわかると思いますが,実は O(NS) で解けます.
分割数のイメージでやるとよいです.DPでやることには変わりません.
dp[i][j] := i 個の異なる数(M以下の数)で,総和を j にする組み合わせ
とすると,遷移は
dp[i][j] = dp[i - 1][j - i] + dp[i][j - i] - dp[i - 1][j - M - 1]
となります.
第1項は,すでに出来ている i - 1個のそれぞれに 1 を加算し,i 番目に 1 を付け加えるという操作を表します.
第2項は,すでに出来ている i 個の数のそれぞれに 1 を加算してできるという意味を表します.
最後の項は,1を加算したことで M を超えるような場合の数を取り除くためのものです.dp[i][j] で M を超えるとしたら,遷移の仕方からその値は M + 1 で,かつその1つだけです.そのような場合の数は,他の i - 1 個の総和が j - M - 1 で,かつ M を超えるものが無い場合なので,dp[i - 1][j - M - 1] に対応します.

以上で O(NS) で解けました.

ソースコード

#include <bits/stdc++.h>
using namespace std;

using pii = pair<int, int>;
using vi = vector<int>;
using ll = long long;

constexpr int mod = 1e9 + 7;

int main() {
    int N, M, S;
    while(cin >> N >> M >> S, N) {
        vector<vector<int>> dp(N * N + 1, vector<int>(S + 1));
        dp[0][0] = 1;
        for(int i = 1; i <= N * N; ++i) {
            for(int j = 0; j <= S; ++j) {
                if(i <= j) {
                    dp[i][j] += dp[i][j - i] + dp[i - 1][j - i];
                }
                if(j - M - 1 >= 0) {
                    dp[i][j] -= dp[i - 1][j - M - 1];
                }
                dp[i][j] = (dp[i][j] + mod) % mod;
            }
        }
        cout << dp[N * N][S] << endl;
    }
}

感想

制約を N <= 100, S <= 10^5, M <= 10^5 にするだけで解けなくなる人が出てきそう.

AOJ 1281 The Morning after Halloween

解法

この問題はやるだけなんですが,TLEとMLEをうまく回避するのが大切な問題です.定数倍遅くなりそうな部分はできるだけ排除していく必要があります.
基本BFSをやっていくだけなのですが,最短距離を short で持つようにするとMLEが防げます.
遷移する部分は,とりあえず3つ文字があると仮定した 5^3 のループ(動かない+4方向に動く)を書いて,適宜つじつまを合わせる実装が楽だと思います.
移動先が壁かどうかの判定を,面倒だからと一番深いループの位置でやるとTLEするので,各文字の遷移先を決めるループごとに枝刈りしないといけません.

あとは変なことを書かなければぎりぎり通ると思います(白目).

ソースコード

#include <bits/stdc++.h>
using namespace std;

using pii = pair<int, int>;

constexpr int dx[5] = {0, 0, 1, 0, -1};
constexpr int dy[5] = {0, 1, 0, -1, 0};

short d[256][256][256];

void init() {
    for(int i = 0; i < 256; ++i) {
        for(int j = 0; j < 256; ++j) {
            for(int k = 0; k < 256; ++k) {
                d[i][j][k] = 10000;
            }
        }
    }
}

bool move_check(int prev1, int to1, int prev2, int to2) {
    return to1 != to2 && (prev1 != to2 || prev2 != to1);
}

int main() {
    int w, h, n;
    while(cin >> w >> h >> n, n) {
        init();
        vector<string> c(h);
        vector<pii> cs1, cs2;
        cin.ignore(1000, '\n');
        for(int i = 0; i < h; ++i) {
            getline(cin, c[i]);
            for(int j = 0; j < w; ++j) {
                if('a' <= c[i][j] && c[i][j] <= 'z') {
                    cs1.emplace_back(c[i][j], i * w + j);
                }
                if('A' <= c[i][j] && c[i][j] <= 'Z') {
                    cs2.emplace_back(c[i][j], i * w + j);
                }
            }
        }
        sort(begin(cs1), end(cs1));
        sort(begin(cs2), end(cs2));
        array<int, 3> s = {255, 255, 255}, g = {255, 255, 255};
        for(int i = 0; i < n; ++i) {
            s[i] = cs1[i].second;
            g[i] = cs2[i].second;
        }

        queue<pair<array<int, 3>, short>> que;
        d[s[0]][s[1]][s[2]] = 0;
        que.emplace(s, 0);
        int res = 0;
        while(!que.empty()) {
            auto now = que.front().first;
            auto cost = que.front().second;
            que.pop();
            if(now == g) {
                res = cost;
                break;
            }
            for(int i = 0; i < 5; ++i) {
                int ny0 = now[0] / w + dy[i], nx0 = (now[0] % w) + dx[i];
                if(c[ny0][nx0] == '#') {
                    continue;
                }
                for(int j = 0; j < 5; ++j) {
                    int ny1 = now[1] / w + dy[j], nx1 = (now[1] % w) + dx[j];
                    if(n >= 2 && c[ny1][nx1] == '#') {
                        continue;
                    }
                    for(int k = 0; k < 5; ++k) {
                        int ny2 = now[2] / w + dy[k], nx2 = (now[2] % w) + dx[k];
                        if(n == 3 && c[ny2][nx2] == '#') {
                            continue;
                        }
                        array<int, 3> nxt = {ny0 * w + nx0,
                                             (n >= 2 ? ny1 * w + nx1 : 255),
                                             (n == 3 ? ny2 * w + nx2 : 255)};
                        bool move_ok = true;
                        for(int l = 0; n != 1 && l < n; ++l) {
                            move_ok &= move_check(now[l], nxt[l], now[(l + 1) % n], nxt[(l + 1) % n]);
                        }
                        if(move_ok && d[nxt[0]][nxt[1]][nxt[2]] == 10000) {
                            d[nxt[0]][nxt[1]][nxt[2]] = cost + 1;
                            que.emplace(nxt, cost + 1);
                        }
                    }
                }
            }
        }
        cout << res << endl;
    }
}

感想

まあ,最初サボりすぎてTLE食らったんですけどね.実装はきれいに書けたほうだと思う.(速度が早いとは言ってない)
ちなみに 5.50 s / 8.00 s です.あぶねえな.
ケースによるけど,n が小さいならループを回さないようにしたほうが早くはなると思う.でも全部 n == 3 だと意味ないからそういうふうには書かなかった.

A* とか 両側探索だと多少早いのかな?

AOJ 1238 True Liars

解法

人をノードと見て,x y a を辺と考えると良い.ある人を仮に divine あるいは delivish と定めると,その人と関係のある人間の性質が一意に定まる.
よって,関係のあるグループについて2通りを試して,その結果で dp をすればよい.
・dp[i][j][k] := i 番目のグループまで見て,divine が j 人であり,delivish が k 人である時の,直前のグループの状態
とする.直前のグループの状態は,代表の id と,その人の性質,そしてそのグループの分配の仕方を表す.
同じ dp[i][j][k] に到達する状態が複数あった場合,以降その状態とそこから遷移できるすべての状態を ambiguous に設定してしまう.
最後に dp.back()[p1][p2] が有効なら復元していく.

ソースコード

#include <bits/stdc++.h>
using namespace std;

using pii = pair<int, int>;

struct edge {
    int to;
    bool yes;
};

using edges = vector<edge>;
using graph = vector<edges>;

// (divine, devilish)
pii dfs(graph const& g, int v, bool divine, vector<bool>& checked) {
    auto res = make_pair((int)divine, (int)!divine);
    checked[v] = true;
    for(auto& e : g[v]) {
        if(checked[e.to]) {
            continue;
        }
        bool next_state = (divine && e.yes || !divine && !e.yes);
        auto t = dfs(g, e.to, next_state, checked);
        res.first += t.first;
        res.second += t.second;
    }
    return res;
}

void determine(graph const& g, int v, bool divine, vector<int>& res) {
    res[v] = divine;
    for(auto& e : g[v]) {
        if(res[e.to] != -1) {
            continue;
        }
        bool next_state = (divine && e.yes || !divine && !e.yes);
        determine(g, e.to, next_state, res);
    }
}

struct data {
    int person_id;
    bool divine;
    pii each_num; // (divine, devilish)
    data() : person_id(-1), divine(false), each_num(make_pair(0, 0))
    {}
};

int main() {
    int n, p1, p2;
    while(cin >> n >> p1 >> p2, n || p1 || p2) {
        graph g(p1 + p2);
        if(n == 0) {
            if(p2 == 0) {
                for(int i = 1; i <= p1 + p2; ++i) {
                    cout << i << endl;
                }
            } else if(p1 != 0) {
                cout << "no" << endl;
                continue;
            }
            cout << "end" << endl;
            continue;
        }
        for(int i = 0; i < n; ++i) {
            int x, y;
            string a;
            cin >> x >> y >> a;
            g[x - 1].push_back(edge{y - 1, a == "yes"});
            g[y - 1].push_back(edge{x - 1, a == "yes"});
        }
        vector<vector<vector<data>>> dp(1, vector<vector<data>>(p1 + 1, vector<data>(p2 + 1)));
        dp[0][0][0].person_id = 0;
        vector<bool> checked(p1 + p2);
        for(int i = 0; i < p1 + p2; ++i) {
            auto now = dp.back();
            vector<vector<data>> nxt(p1 + 1, vector<data>(p2 + 1));
            if(!checked[i]) {
                for(int b = 0; b <= 1; ++b) {
                    data d;
                    d.person_id = i;
                    d.divine = b;
                    auto checked2 = checked;
                    d.each_num = dfs(g, i, b, checked);
                    if(b == 0) {
                        checked = checked2; // restore
                    }
                    for(int j = 0; j <= p1; ++j) {
                        for(int k = 0; k <= p2; ++k) {
                            if(now[j][k].person_id == -1) {
                                continue;
                            }
                            int nj = j + d.each_num.first, nk = k + d.each_num.second;
                            if(nj > p1 || nk > p2 || nxt[nj][nk].person_id == -2) {
                                continue;
                            }
                            if(nxt[nj][nk].person_id >= 0 || now[j][k].person_id == -2) { // ambiguous
                                nxt[nj][nk].person_id = -2;
                                continue;
                            }
                            nxt[nj][nk] = d;
                        }
                    }
                }
                dp.push_back(move(nxt));
            }
        }
        auto now = dp.back()[p1][p2];
        if(now.person_id < 0) {
            cout << "no" << endl;
        } else {
            vector<int> res(p1 + p2, -1);
            int P1 = p1, P2 = p2;
            for(int i = dp.size() - 1; i > 0; --i) {
                auto d = dp[i][P1][P2];
                determine(g, d.person_id, d.divine, res);
                P1 -= d.each_num.first;
                P2 -= d.each_num.second;
            }
            for(int i = 0; i < p1 + p2; ++i) {
                if(res[i] == 1) {
                    cout << i + 1 << endl;
                }
            }
            cout << "end" << endl;
        }
    }
}

感想

まあすぐわかると思うんですが,実装方針が良くないです.特に,dp[i][j][k] としているのが悪くて,j の値がわかれば k の値は自動的に決まるため,片方を保つ必要はありません.実装方針どころか,計算量が変わるので非常にまずいです.(今回は十分間に合いますけどね.)
また,ambiguous な状態の表現は,そうなる遷移の数を dp の値として持つことで自然に表現できるため,変な負の値を割り当てずにそうすべきだったかな.
あとは data 構造体で持つのではなく,複数の配列に分けて持ったほうがきれいかもしれない.これは好みかな?

AOJ 2731 Shifting a Matrix

解説

シフト操作 F について,F[i][j] := i 行目 j 列目の要素がどこに移るか と表現すれば,あとはこれらを結合するだけです.操作 F, G に対し,これらをこの順に結合した操作 H は H[i][j] = F[G[i][j].first][G[i][j].second] と計算できます.
操作回数が大きいので,行列のシフト操作は繰り返し二乗法っぽく計算します.
変に解説するよりコードを読んでもらったほうが早いと思います.

ソースコード

#include <bits/stdc++.h>
using namespace std;

using pii = pair<int, int>;

int N;

vector<vector<pii>> make_initial() {
    vector<vector<pii>> res(N, vector<pii>(N));
    for(int i = 0; i < N; ++i) {
        for(int j = 0; j < N; ++j) {
            res[i][j] = make_pair(i, j);
        }
    }
    return res;
}

vector<vector<pii>> eval(vector<vector<pii>> const& A, vector<vector<pii>> const& x) {
    auto res = A;
    for(int i = 0; i < N; ++i) {
        for(int j = 0; j < N; ++j) {
            res[i][j] = A[x[i][j].first][x[i][j].second];
        }
    }
    return res;
}

vector<vector<pii>> sequence(string const& s, int& p);
vector<vector<pii>> repetition(string const& s, int& p);
vector<vector<pii>> operation(string const& s, int& p);
int number(string const& s, int& p);

vector<vector<pii>> sequence(string const& s, int& p) {
    auto res = make_initial();
    while(p < s.size() && (s[p] == '(' || isalpha(s[p]))) {
        vector<vector<pii>> f;
        if(s[p] == '(') {
            f = repetition(s, p);
        } else if(isalpha(s[p])) {
            f = operation(s, p);
        } else {
            cout << "error pos: " << p << endl;
            assert(false); // error
        }
        res = eval(res, f);
    }
    return res;
}

vector<vector<pii>> repetition(string const& s, int& p) {
    auto x = sequence(s, ++p);
    ++p;
    assert(isdigit(s[p]));
    int n = number(s, p);
    auto res = make_initial();
    while(n > 0) {
        if(n & 1) {
            res = eval(res, x);
        }
        x = eval(x, x);
        n >>= 1;
    }
    return res;
}

vector<vector<pii>> operation(string const& s, int& p) {
    auto res = make_initial();
    char op = s[p++];
    int i = number(s, p) - 1;
    if(op == 'L') {
        for(int j = 0; j < N; ++j) {
            res[i][j].second = (j + 1) % N;
        }
    } else if(op == 'R') {
        for(int j = 0; j < N; ++j) {
            res[i][j].second = (j - 1 + N) % N;
        }
    } else if(op == 'U') {
        for(int j = 0; j < N; ++j) {
            res[j][i].first = (j + 1) % N;
        }
    } else if(op == 'D') {
        for(int j = 0; j < N; ++j) {
            res[j][i].first = (j - 1 + N) % N;
        }
    } else {
        assert(false);
    }
    return res;
}

int number(string const& s, int& p) {
    int res = 0;
    while(isdigit(s[p])) {
        res *= 10;
        res += (s[p++] - '0');
    }
    return res;
}

int main() {
    int L;
    string S;
    cin >> N >> L >> S;
    int p = 0;
    auto ans = sequence(S, p);
    for(int i = 0; i < N; ++i) {
        for(int j = 0; j < N; ++j) {
            cout << (ans[i][j].first * N + ans[i][j].second + 1) << " \n"[j + 1 == N];
        }
    }
}

感想

構文解析アルゴリズムの知識,実装パートのそれぞれが良いパランスで要求されている教育的良問だと思う.難易度もあまり高くない.
写像の表現は pair でやったけど,(i, j) -> i * N + j と一次元に直したほうが楽かもしれない.

AOJ 1361 Deadlock Detection

解法

求めるものは unavoidable になる境界なので二分探索できそうです.
ある時刻からデットロックを避ける最良の方法は,当然 terminate できるプロセスを順に殺していくことです.
愚直にやると殺せるプロセスを探索するのに O(p^2r) かかりそうですが,あらかじめリソースごとに必要な数でソートしておくと O(prlog(p)) でできるようになります.
計算量はトータル O( (t + prlogp)logt) になります.

ソースコード

#include <bits/stdc++.h>
using namespace std;

using pii = pair<int, int>;

int main() {
    int p, r, t;
    cin >> p >> r >> t;
    vector<int> l(r);
    vector<vector<int>> n(p, vector<int>(r));
    vector<int> P(t), R(t);
    for(int i = 0; i < r; ++i) {
        cin >> l[i];
    }
    for(int i = 0; i < p; ++i) {
        for(int j = 0; j < r; ++j) {
            cin >> n[i][j];
        }
    }
    for(int i = 0; i < t; ++i) {
        cin >> P[i] >> R[i];
        P[i]--; R[i]--;
    }

    int lb = 0, ub = t + 1;
    while(ub - lb > 1) {
        int m = (lb + ub) / 2;
        vector<int> available = l;
        vector<vector<pii>> need_r(r, vector<pii>(p));
        vector<vector<int>> used_r(p, vector<int>(r));
        vector<int> pos(r), cnt(p);
        queue<int> term_process;
        for(int i = 0; i < r; ++i) {
            for(int j = 0; j < p; ++j) {
                need_r[i][j] = make_pair(n[j][i], j);
            }
        }
        for(int i = 0; i < m; ++i) {
            available[R[i]]--;
            need_r[R[i]][P[i]].first--;
            used_r[P[i]][R[i]]++;
        }
        for(int i = 0; i < r; ++i) {
            sort(begin(need_r[i]), end(need_r[i]));
        }
        for(int i = 0; i < r; ++i) {
            while(pos[i] < p && (need_r[i][pos[i]].first == 0 || available[i] >= need_r[i][pos[i]].first)) {
                int process_id = need_r[i][pos[i]].second;
                if(++cnt[process_id] == r) {
                    term_process.push(process_id);
                }
                pos[i]++;
            }
        }
        while(!term_process.empty()) {
            int idx = term_process.front();
            term_process.pop();
            for(int i = 0; i < r; ++i) {
                available[i] += used_r[idx][i];
                while(pos[i] < p && available[i] >= need_r[i][pos[i]].first) {
                    int process_id = need_r[i][pos[i]].second;
                    if(++cnt[process_id] == r) {
                        term_process.push(process_id);
                    }
                    pos[i]++;
                }
            }
        }
        if(count(begin(cnt), end(cnt), r) == p) {
            lb = m;
        } else {
            ub = m;
        }
    }
    if(ub == t + 1) {
        cout << -1 << endl;
    } else {
        cout << ub << endl;
    }
}

感想

やるだけなんですがバグってしまった.

AOJ 1362 Do Geese See God?

問題概要

文字列 S を部分列(部分文字列ではない)に持つような最小の長さの回文の集合の中で,辞書順 k 番目のものを求めよ.
・制約
1 <= |S| <= 2000
1 <= k <= 10^18

解法

区間DPをやります.作れる文字列の数 + 辞書順最小構築が必要なので,DPかなあという推測は立つと思います.

まず,問題を2つの部分に分けます.

  1. 最小の文字列の長さを求める
  2. 作ることのできる回文のパターン数

最小の文字列の長さは,以下の dp で求められます.
len[i][j] := S[i, j] を部分列にもつような回文の最小長さ
右端と左端が一致していない場合,最小の回文を構成するのであれば,そのどちらかを挿入することになります.一致していれば,明らかに挿入する必要はありません.これを元に漸化式を立てます.

作ることのできる回文のパターン数も,以下の dp で求められます.
dp[i][j] := S[i, j] を部分列にもつような最小長さの回文の種類数
この計算には len[i][j] を用います.S[i] と S[j] が等しい場合,最小長さにするので dp[i + 1][j - 1] が答えです.S[i] と S[j] が異なる場合,S[i] と S[j] のどちらかを挿入することになりますが,len[i + 1][j] と len[i][j - 1] の値の大小によって,どちらを挿入するべきか判定できます.(もちろん小さくなる方を挿入する.)
挿入するほうが決まれば,そのときの dp[i + 1][j] または dp[i][j - 1] の値を加算します.

dp[0][n - 1] < K なら答えはありません.

最後に構築パートですが,これはいつものやつなので雑に書きます.
S[l] == S[r] ならその文字を使うことが確定します.
S[l] != S[r] なら,短くなるほうを選びます.どちらをえらんでも同じ長さを達成できるなら小さい方を使いたいですが,K を超えないギリギリに向かうように選ぶ必要もあります.

ソースコード

#include <bits/stdc++.h>
using namespace std;
 
using ll = long long;
 
constexpr int INF = 1e9;
constexpr ll INFLL = 1e18;
 
ll add(ll& a, ll b) {
    return a = min(a + b, INFLL * 2);
}
 
int main() {
    string S;
    ll K;
    cin >> S >> K;
    int const n = S.size();
    vector<vector<int>> len(n, vector<int>(n, INF));
    for(int i = n - 1; i >= 0; --i) {
        len[i][i] = 1;
        for(int j = i + 1; j < n; ++j) {
            if(S[i] == S[j]) {
                len[i][j] = (i + 1 == j ? 2 : len[i + 1][j - 1] + 2);
            }
            len[i][j] = min(len[i][j], min(len[i + 1][j], len[i][j - 1]) + 2);
        }
    }
    vector<vector<ll>> dp(n, vector<ll>(n));
    for(int i = n - 1; i >= 0; --i) {
        dp[i][i] = 1;
        for(int j = i + 1; j < n; ++j) {
            if(S[i] == S[j]) {
                add(dp[i][j], (i + 1 == j ? 1 : dp[i + 1][j - 1]));
            } else {
                int min_len = min(len[i + 1][j], len[i][j - 1]);
                if(len[i + 1][j] == min_len) {
                    add(dp[i][j], dp[i + 1][j]);
                }
                if(len[i][j - 1] == min_len) {
                    add(dp[i][j], dp[i][j - 1]);
                }
            }
        }
    }
 
    if(dp[0][n - 1] < K) {
        cout << "NONE" << endl;
        return 0;
    }
 
    ll t = 1;
    string l_ans;
    int l = 0, r = n - 1;
    while(l < r) {
        if(S[l] == S[r]) {
            l_ans += S[l++];
            r--;
        } else {
            if(len[l + 1][r] < len[l][r - 1]) {
                l_ans += S[l++];
            } else if(len[l + 1][r] > len[l][r - 1]) {
                l_ans += S[r--];
            } else {
                ll t2 = t + (S[l] < S[r] ? dp[l + 1][r] : dp[l][r - 1]);
                if(t2 > K && S[l] < S[r] || t2 <= K && S[l] > S[r]) {
                    l_ans += S[l++];
                } else {
                    l_ans += S[r--];
                }
                if(t2 <= K) {
                    t = t2;
                }
            }
        }
    }
    auto r_ans = l_ans;
    reverse(begin(r_ans), end(r_ans));
    if(l == r) {
        l_ans += S[l];
    }
    cout << l_ans + r_ans << endl;
}

感想

こういう問題は苦手.

AGC001 C - Shorten Diameter

解法

解説と(ちょっとだけ)違ったので一応書いておきます.
まずBFSで全点対最短路を求めておいて,頂点 v から K より離れた頂点の数を sz[v] とします.
あとは sz[v] の大きい方から貪欲に削除していきます. v を消した時,関係のある w に対して sz[w] の値をデクリメントすれば良いです.
これは O(N^2) でできます.

ソースコード

#include <bits/stdc++.h>
using namespace std;

using ll = long long;

constexpr int INF = 1e9;

vector<int> bfs(vector<vector<int>> const& g, int s) {
    int const n = g.size();
    vector<int> d(n, INF);
    d[s] = 0;
    queue<int> que;
    que.push(s);
    while(!que.empty()) {
        int v = que.front();
        que.pop();
        for(auto to : g[v]) {
            if(d[to] != INF) {
                continue;
            }
            d[to] = d[v] + 1;
            que.push(to);
        }
    }
    return d;
}

int main() {
    int N, K;
    cin >> N >> K;
    vector<vector<int>> g(N);
    for(int i = 0; i < N - 1; ++i) {
        int a, b;
        cin >> a >> b;
        a--; b--;
        g[a].push_back(b);
        g[b].push_back(a);
    }

    vector<vector<int>> vs(N);
    vector<int> sz(N);
    for(int i = 0; i < N; ++i) {
        auto d = bfs(g, i);
        for(int j = 0; j < N; ++j) {
            if(d[j] > K) {
                vs[i].push_back(j);
                sz[i]++;
            }
        }
    }

    int res = 0;
    while(true) {
        auto it = max_element(sz.begin(), sz.end());
        if(*it == 0) {
            break;
        }
        int v = it - sz.begin();
        sz[v] = 0;
        for(auto w : vs[v]) {
            sz[w]--;
        }
        vs[v].clear();
        res++;
    }
    cout << res << endl;
}

感想

証明してないけど,sz[v] が K より大きいものをできるだけ一気に減らしたいわけで,それはつまり sz[v] が大きい方を消せばデクリメントが一気にできるから嬉しいよね,みたいな.