AOJ 2294 Entangled with Lottery

解法

ゴールから見るDPでやります.

dp[i][j][k] := 高さ (H から) i まで見た時に,位置 j にいて,それまでに猫が k 本引いているような確率

とします.
高さ 1 から i までに,うさぎがすでに引いている本数を m とすると,猫が引ける高さは残り i - m 箇所です.
今見ている高さがすでにうさぎによって線が引かれていれば,単純に swap するだけです.
引かれていないなら,今見ている高さに猫が線を引く確率 q は,
$\displaystyle q = \frac{_{i - m - 1}C_{K - k - 1}}{_{i - m}C_{K - k}} = \frac{K - k}{i - m}$
となります.
引いた上で,今見ている位置 j に関係する部分に線が引かれる確率 p は,端ならば $\displaystyle p = \frac{1}{N - 1}$,端でなければ $\displaystyle \frac{2}{N - 1}$ です.
あとは,dp[i][j][k] を,「その高さに線をそもそも引かない」「その高さに線を引き,かつそれが j に関係する」「その高さに線を引き,かつそれが j に関係しない」場合の3つに遷移させるだけです.

ソースコード

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

using pii = pair<int, int>;

int main() {
    cout << fixed << setprecision(10);
    int H, N, P, M, K;
    cin >> H >> N >> P >> M >> K;
    P--;
    vector<int> sw(H, -1);
    for(int i = 0; i < M; ++i) {
        int a, b;
        cin >> a >> b;
        sw[a - 1] = b - 1;
    }

    vector<int> sum(H + 1);
    for(int i = 0; i < H; ++i) {
        sum[i + 1] = sum[i] + (sw[i] != -1);
    }
    vector<vector<double>> dp(N, vector<double>(K + 1));
    dp[P][0] = 1;
    double p = 1.0 / (N - 1);
    for(int i = H - 1; i >= 0; --i) {
        vector<vector<double>> nxt(N, vector<double>(K + 1));
        for(int j = 0; j < N; ++j) {
            for(int k = 0; k <= K; ++k) {
                if(dp[j][k] == 0) {
                    continue;
                }
                if(sw[i] == -1) {
                    double q = (double)(K - k) / (i + 1 - sum[i]); // put possibility
                    if(k == K) {
                        nxt[j][k] += dp[j][k] * (1 - q); // (1 - q) == 1
                    } else {
                        if(j != 0) {
                            nxt[j - 1][k + 1] += dp[j][k] * p * q;
                        }
                        if(j != N - 1) {
                            nxt[j + 1][k + 1] += dp[j][k] * p * q;
                        }
                        nxt[j][k] += dp[j][k] * (1 - q);
                        if(j == 0 || j == N - 1) {
                            nxt[j][k + 1] += dp[j][k] * q * (N - 2) / (N - 1);
                        } else {
                            nxt[j][k + 1] += dp[j][k] * q * (N - 3) / (N - 1);
                        }
                    }
                } else {
                    if(sw[i] == j) {
                        nxt[sw[i] + 1][k] += dp[j][k];
                    } else if(sw[i] + 1 == j) {
                        nxt[sw[i]][k] += dp[j][k];
                    } else {
                        nxt[j][k] += dp[j][k];
                    }
                }
            }
        }
        dp = move(nxt);
    }

    double res = 0;
    for(int i = 0; i < N; ++i) {
        res = max(res, dp[i][K]);
    }
    cout << res << endl;
}

AOJ 2556 Integer in Integer

解法

やり方は色々あると思うんですが,僕は桁DPっぽくやりました(正直実装方針かなりミスっていると思う.)

まず,[0..N] までの答え f(N) を求めることができれば,f(B) - f(A - 1) で求められるので,f(N) を考えましょう.

dp[i][j][k] := i 桁目まで見たときに,C と先頭 j 桁が一致していて,その桁まで見たときに N 以下であるかが k であるような,leading zero を除いた場合の数
dp0[i][j][k] := i 桁目まで見たときに,C と先頭 j 桁が一致していて,その桁まで見たときに N 以下であるかが k であるような,leading zero である場合の数

dp2[i][j][k] := i 桁目まで見たときに,N 以下であるかが j であり,leading zero であるかが k であるようなもので,含まれる C の数

まず dp を計算する前に,C と先頭 j 桁が一致しているときに d (1桁の数)を付け加えたら何桁一致することになるかを match[j][d] として求めておきます(これは全探索で求められる).

match[j][d] をつかって各 dp テーブルを更新していくのですが,流れとしては

  • dp2 で,1桁付け加えていく
  • dp と dp0 を更新する
  • i 桁目で dp と dp0 で C と完全一致するパターンを dp2 に付け加える

という感じになります.コードはごちゃごちゃしてるけど遷移は自然.
dp と dp0 は,あくまで i 桁目までみて先頭が C と一致しているような数を求めているだけにすぎないです(i + 1 桁目以降は存在しないとして数えている).
(例.C = 11 なら,3桁目までみて 11x となるのは 10 通り,2桁目まででは 11 の 1 通り.x の値によって,dp に入るか dp2 に入るかが変わってくる)

答えは dp2[i][0][0] + (i != |N| ? dp2[i][1][0] : 0) の総和です.
C = 0 のときはちょっと注意が必要です.

書いてて自分でもよくわからなくなってきた(???)

オーダーは O(2 * 10 * |C| * |A|) の 10^8 ぐらいで実際はもうちょい遅いかな~ぐらいです.

ソースコード

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

using ll = long long;

constexpr int M = 1e9 + 7;

int solve(string A, string C) {
    int const n = A.size();
    int const m = C.size();
    reverse(A.begin(), A.end());
    reverse(C.begin(), C.end());
    vector<vector<int>> match(m + 1, vector<int>(10));
    for(int d = 0; d <= 9; ++d) {
        char ch = '0' + d;
        for(int i = 0; i <= m; ++i) {
            int len = 0;
            for(int j = min(i + 1, m); j >= 1; --j) {
                if(C.substr(0, j) == C.substr(i - j + 1, j - 1) + ch) {
                    len = j;
                    break;
                }
            }
            match[i][d] = len;
        }
    }
    vector<vector<int>> dp(m + 1, vector<int>(2));
    vector<vector<int>> dp0(m + 1, vector<int>(2)); // leading zero
    vector<vector<vector<int>>> dp2(n + 1, vector<vector<int>>(2, vector<int>(2)));
    dp[0][0] = 1;
    int res = 0;
    for(int i = 0; i < n; ++i) {
        vector<vector<int>> nxt(m + 1, vector<int>(2)), nxt0(m + 1, vector<int>(2));
        for(int k = 0; k < 2; ++k) {
            for(int d = 0; d <= 9; ++d) {
                char ch = '0' + d;
                bool nk = k && ch == A[i] || ch > A[i];
                if(d == 0) {
                    (dp2[i + 1][nk][1] += dp2[i][k][0]) %= M;
                    (dp2[i + 1][nk][1] += dp2[i][k][1]) %= M;
                } else {
                    (dp2[i + 1][nk][0] += dp2[i][k][0]) %= M;
                    (dp2[i + 1][nk][0] += dp2[i][k][1]) %= M;
                }
            }
        }
        for(int j = 0; j <= m; ++j) {
            for(int k = 0; k < 2; ++k) {
                for(int d = 0; d <= 9; ++d) {
                    char ch = '0' + d;
                    bool nk = k && ch == A[i] || ch > A[i];
                    int nj = match[j][d];
                    if(d == 0) {
                        (nxt0[nj][nk] += dp[j][k]) %= M;
                        (nxt0[nj][nk] += dp0[j][k]) %= M;
                    } else {
                        (nxt[nj][nk] += dp[j][k]) %= M;
                        (nxt[nj][nk] += dp0[j][k]) %= M;
                    }
                }
            }
        }
        (dp2[i + 1][0][0] += nxt[m][0]) %= M;
        (dp2[i + 1][0][1] += nxt0[m][0]) %= M;
        (dp2[i + 1][1][0] += nxt[m][1]) %= M;
        (dp2[i + 1][1][1] += nxt0[m][1]) %= M;
        dp = move(nxt);
        dp0 = move(nxt0);
    }

    for(int i = 1; i <= n; ++i) {
        (res += dp2[i][0][0]) %= M;
        if(i != n) {
            (res += dp2[i][1][0]) %= M;
        }
    }
    if(C == "0") {
        (res += 1) % M;
    }
    return res;
}

string decrement(string A) {
    for(int i = A.size() - 1; i >= 0; --i) {
        if(A[i] > '0') {
            A[i]--;
            break;
        } else {
            A[i] = '9';
        }
    }
    if(A[0] == '0' && A.size() > 1) {
        return A.substr(1);
    } else {
        return A;
    }
}

int main() {
    string A, B, C;
    cin >> A >> B >> C;
    if(A != "0") {
        cout << (solve(B, C) - solve(decrement(A), C) + M) % M << endl;
    } else {
        cout << solve(B, C) << endl;
    }
}

感想

通ったからいいけど,桁DPっぽくやったのは失敗だったかなあと思っています.
今真っ白な状態から書くなら,j 桁目が C であるような N 以下の数っていうのを求めていく感じになりそう.[X] ... C ... [Y] の X と Y を N を越えないように数えるみたいな.

AOJ 2614 Almost Same Substring

解法

ローリングハッシュでやります.

同じ長さの文字列 S, T に対して,「左からみて何文字一致しているか」と「右からみて何文字一致しているか」をそれぞれ二分探索で求めます.
もし S と T が一文字だけ異なるなら,左からの一致文字数と右からの一致文字数の和が,長さから1だけ小さいものになっているはずです.

よって,問題で与えられた S, T' について,S[a..a+|T'|-1] と T' に対し,先程やったことをすれば求まります.

ソースコード

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

// 1-indexed
// s[1...n]
class rolling_hash {
public:
    rolling_hash(std::string const& s)
        : n(s.size()),
          mod({999999937LL, 1000000007LL})
    {
        for(int i = 0; i < 2; ++i) {
            hs[i].resize(n + 1);
            p[i].resize(n + 1);
            hs[i][0] = 0;
            p[i][0] = 1;
            for(int j = 0; j < n; ++j) {
                hs[i][j + 1] = (hs[i][j] * base + s[j]) % mod[i];
                p[i][j + 1] = p[i][j] * base % mod[i];
            }
        }
    }

    // s[i...]
    long long query(int idx, int i) const {
        return hs[i][idx];
    }
    // s[l + 1...r]
    long long query(int l, int r, int i) const {
        return ((hs[i][r] - hs[i][l] * p[i][r - l]) % mod[i] + mod[i]) % mod[i];
    }

private:
    int n;
    std::vector<long long> hs[2];
    std::vector<long long> p[2];

    const std::array<long long, 2> mod;
    static const long long base = 29LL;
};

int main() {
    string S, T;
    cin >> S >> T;
    rolling_hash hs1(S), hs2(T);
    int res = 0;
    for(int i = 1; i + T.size() - 1 <= S.size(); ++i) {
        int lb = i - 1, ub = i + T.size();
        while(ub - lb > 1) {
            int m = (ub + lb) / 2;
            if(hs1.query(i - 1, m, 1) == hs2.query(0, m - i + 1, 1)) {
                lb = m;
            } else {
                ub = m;
            }
        }
        int l = lb;
        lb = i - 1, ub = i + T.size();
        while(ub - lb > 1) {
            int m = (ub + lb) / 2;
            if(hs1.query(m - 1, i + T.size() - 1, 1) == hs2.query(m - i, T.size(), 1)) {
                ub = m;
            } else {
                lb = m;
            }
        }
        int r = ub;

        res += l + 2 == r;
    }
    cout << res << endl;
}

感想

ローリングハッシュ使う時いっつもインデックスで混乱する.

AOJ 2605 Social Monsters

解法

制約をよく読むと,(使えない辺を含める)与えられたグラフにおける各連結成分は,1つのパスまたは閉路になっていることがわかります.
各連結成分において計算して,最後にまとめあげることにします.

1つのパスについては,以下のDPで端から順番に計算します.
dp[i][j][k] := i 番目の頂点までみたとき,それまでに j 個の頂点を用いていて,直前の頂点を使ったかのフラグが k であるときの最大値
隣接してる2つが使えないなら,k == 0 となる場合しか今見ている頂点は使えない,みたいな遷移になります.

閉路については,追加で情報が必要です.閉路の始点は適当に決めて良いです.
dp[i][j][k][l] := i 番目の頂点まで見た時,それまでに j 個の頂点を用いていて,直前の頂点を使ったかのフラグが k であり,最初の頂点を使ったかのフラグが l であるときの最大値

最後に各連結成分でもとめた dp の値を合わせて全体の結果を得ます.

ソースコード

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

constexpr int INF = 1e9;

struct edge {
    int to, cost;
};

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

int N, M, K;
int cost[2001][2001];

// true -> circuit
bool dfs(graph const& g, int v, int p, vector<bool>& visited, vector<int>& res) {
    res.push_back(v);
    visited[v] = true;
    bool circuit = false;
    for(auto& e : g[v]) {
        if(e.to == p) {
            continue;
        }
        if(visited[e.to]) {
            circuit = true;
        } else {
            circuit |= dfs(g, e.to, v, visited, res);
        }
    }
    return circuit;
}

vector<int> calc_line(vector<int> const& line) {
    vector<vector<int>> dp(K + 1, vector<int>(2, -INF));
    dp[0][0] = dp[1][1] = 0;
    for(int i = 1; i < (int)line.size(); ++i) {
        int pre = line[i - 1];
        int v = line[i];
        vector<vector<int>> nxt(K + 1, vector<int>(2, -INF));
        for(int k = 0; k <= K; ++k) {
            if(dp[k][0] != -INF) {
                if(k + 1 <= K) {
                    nxt[k + 1][1] = max(nxt[k + 1][1], dp[k][0]);
                }
                nxt[k][0] = max(nxt[k][0], dp[k][0]);
            }
            if(dp[k][1] != -INF) {
                if(cost[pre][v] != 0 && k + 1 <= K) {
                    nxt[k + 1][1] = max(nxt[k + 1][1], dp[k][1] + cost[pre][v]);
                }
                nxt[k][0] = max(nxt[k][0], dp[k][1]);
            }
        }
        dp.swap(nxt);
    }

    vector<int> res(K + 1);
    for(int i = 0; i < K + 1; ++i) {
        res[i] = max(dp[i][0], dp[i][1]);
    }
    return res;
}

vector<int> calc_cycle(vector<int> const& cycle) {
    // (use, pre, first)
    vector<vector<vector<int>>> dp(K + 1, vector<vector<int>>(2, vector<int>(2, -INF)));
    dp[0][0][0] = dp[1][1][1] = 0;
    int const first = cycle[0];
    for(int i = 1; i < (int)cycle.size(); ++i) {
        int pre = cycle[i - 1];
        int v = cycle[i];
        vector<vector<vector<int>>> nxt(K + 1, vector<vector<int>>(2, vector<int>(2, -INF)));
        for(int k = 0; k <= K; ++k) {
            for(int fuse = 0; fuse <= 1; ++fuse) {
                if(i == cycle.size() - 1 && fuse == 1) {
                    if(dp[k][0][fuse] != -INF) {
                        if(k + 1 <= K && cost[first][v] != 0) {
                            nxt[k + 1][1][fuse] = max(nxt[k + 1][1][fuse], dp[k][0][fuse] + cost[first][v]);
                        }
                        nxt[k][0][fuse] = max(nxt[k][0][fuse], dp[k][0][fuse]);
                    }
                    if(dp[k][1][fuse] != -INF) {
                        if(cost[first][v] != 0 && cost[pre][v] != 0 && k + 1 <= K) {
                            nxt[k + 1][1][fuse] = max(nxt[k + 1][1][fuse], dp[k][1][fuse] + cost[pre][v] + cost[first][v]);
                        }
                        nxt[k][0][fuse] = max(nxt[k][0][fuse], dp[k][1][fuse]);
                    }
                } else {
                    if(dp[k][0][fuse] != -INF) {
                        if(k + 1 <= K) {
                            nxt[k + 1][1][fuse] = max(nxt[k + 1][1][fuse], dp[k][0][fuse]);
                        }
                        nxt[k][0][fuse] = max(nxt[k][0][fuse], dp[k][0][fuse]);
                    }
                    if(dp[k][1][fuse] != -INF) {
                        if(cost[pre][v] != 0 && k + 1 <= K) {
                            nxt[k + 1][1][fuse] = max(nxt[k + 1][1][fuse], dp[k][1][fuse] + cost[pre][v]);
                        }
                        nxt[k][0][fuse] = max(nxt[k][0][fuse], dp[k][1][fuse]);
                    }
                }
            }
        }
        dp.swap(nxt);
    }

    vector<int> res(K + 1);
    for(int i = 0; i < K + 1; ++i) {
        res[i] = max({dp[i][0][0], dp[i][0][1], dp[i][1][0], dp[i][1][1]});
    }
    return res;
}

int main() {
    cin >> N >> M >> K;
    graph g(N);
    for(int i = 0; i < M; ++i) {
        int a, b, c;
        cin >> a >> b >> c;
        a--; b--;
        g[a].push_back(edge{b, c});
        g[b].push_back(edge{a, c});
        cost[a][b] = cost[b][a] = c;
    }

    vector<vector<int>> line, cycle;
    vector<bool> visited(N);
    vector<int> sz;
    for(int i = 0; i < N; ++i) {
        if(!visited[i]) {
            vector<int> c;
            bool circuit = dfs(g, i, -1, visited, c);
            if(!circuit) {
                for(auto v : c) {
                    visited[v] = false;
                }
                for(auto v : c) {
                    if(g[v].size() == 1) {
                        c.clear();
                        dfs(g, v, -1, visited, c);
                        break;
                    }
                }
                sz.push_back(c.size());
                line.push_back(move(c));
            } else {
                cycle.push_back(move(c));
            }
        }
    }
    for(auto& c : cycle) {
        sz.push_back(c.size());
    }

    vector<vector<int>> dp2;
    for(auto& l : line) {
        dp2.push_back(calc_line(l));
    }
    for(auto& c : cycle) {
        dp2.push_back(calc_cycle(c));
    }

    vector<int> dp(K + 1, -INF);
    dp[0] = 0;
    int total_sz = 0;
    for(int i = 0; i < (int)dp2.size(); ++i) {
        vector<int> nxt(K + 1, -INF);
        for(int k1 = 0; k1 <= total_sz; ++k1) {
            if(dp[k1] == -INF) {
                continue;
            }
            for(int k2 = 0; k2 <= sz[i] && k1 + k2 <= K; ++k2) {
                if(dp2[i][k2] != -INF) {
                    nxt[k1 + k2] = max(nxt[k1 + k2], dp[k1] + dp2[i][k2]);
                }
            }
        }
        total_sz += sz[i];
        dp.swap(nxt);
    }
    if(dp[K] == -INF) {
        cout << "Impossible" << endl;
    } else {
        cout << dp[K] << endl;
    }
}

感想

実装が重い.うまくやれば実装量は減りそうだが,半分ぐらいは同じことをしてるコードなので,コード長の割には楽だったかもしれない.

AOJ 2449 Connect

解法

これは典型問題です.
$i$ 行目の $j$ 番目に文字を置くかどうか考えた時に関係してくるのは,$i$ 行目の $1$ から $j - 1$ 列目と,$i - 1$ 行目の $j$ から $C$ 列目だけです.
なので結局,一行分の状態をビットで持つ bitDP にできます.

$dp[i][j][S] := i$ 行目の $j$ 列目まで見た時,文字が配置されている状況が $S$ であるときの最大値
$S$ の下位 $j$ ビットが今の行の状態,上位 $C - j$ ビットが直前の行の状態を表しています.

$i$ 行目 $j$ 列目の位置に文字を配置する場合,直前に同じ文字が置かれているかと,前の行の同じ列に同じ文字が置かれているかを見ます.
今配置しようとしている文字のインデックスは $bitcount(S \& (1 << j) - 1)$ で得られます.
上の行で配置されている文字のインデックスは,後ろから何番目であるかを考えれば,$|s_i| - bitcount(S >> j)$ で得られます.

使わない選択をする場合は,あとに配置できる余地が十分であるかを確認する必要があります.
その他,$S$ の状態でありえないものは適宜無視すればよいです.

ソースコード

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

int main() {
    int R, C;
    cin >> R >> C;
    vector<string> s(R);
    for(int i = 0; i < R; ++i) {
        cin >> s[i];
    }
    vector<int> bitcount(1 << C);
    for(int i = 0; i < 1 << C; ++i) {
        bitcount[i] = __builtin_popcount(i);
    }

    vector<int> dp(1 << C, -1);
    dp[0] = 0;
    for(int i = 0; i < R; ++i) {
        for(int j = 0; j < C; ++j) {
            vector<int> nxt(1 << C, -1);
            for(int S = 0; S < (1 << C); ++S) {
                if(dp[S] == -1) {
                    continue;
                }
                int idx = bitcount[S & (1 << j) - 1];
                if(idx < s[i].size()) {
                    int t = dp[S];
                    if(idx > 0 && (S & 1 << (j - 1)) && s[i][idx - 1] == s[i][idx]) {
                        t++;
                    }
                    if(i > 0 && (S & 1 << j) && s[i][idx] == s[i - 1][s[i - 1].size() - bitcount[S >> j]]) {
                        t++;
                    }
                    nxt[S | 1 << j] = max(nxt[S | 1 << j], t);
                }
                if(C - j > s[i].size() - idx) {
                    nxt[S & ~(1 << j)] = max(nxt[S & ~(1 << j)], dp[S]);
                }
            }
            dp.swap(nxt);
        }
    }
    cout << 2 * *max_element(begin(dp), end(dp)) << endl;
}

AOJ 2376 Disconnected Game

解法

石取りゲームだからいい感じにわかるんでは?と思ったけどよくわかんなかったのでメモ化再帰で解きます.

勝ちが決まるタイミングはは,連結成分の数が2であり,かつ自分の手番で辺を追加すると,追加できる辺の数が 0 になるときですね.(それはそう)
それまでは,異なる連結成分を連結させるか,連結成分内の頂点同士に辺を張るかのどちらかです.

残りの辺の数は愚直にもたずに偶奇で判定できますね.異なる連結成分同士を結ぶ辺以外で使える辺の数を $unused$ とします.

異なる連結成分同士を結んだ時,$unused$ も変化しますが,偶奇だけわかればいいので,連結成分のサイズの偶奇の情報を持つだけでいいです.
今,サイズが奇数,偶数の連結成分の数を $(odd, even)$ とします.

$(odd, even, unused)$ でメモ化再帰します.
自分の手番でできるパターンは以下の4通りあります.

  • 大きさが偶数の連結成分同士を結ぶ.結果として,偶数の連結成分が1つ減り,新たに使える辺が奇数本増える.
  • 大きさが奇数の連結成分同士を結ぶ.結果として,奇数の連結成分が2つ減り,偶数の連結成分が1つ増える.また,使える辺の数が偶数本増える.
  • 大きさが偶数と奇数の連結成分を結ぶ.結果として,偶数の連結成分が1つ減る.また,使える辺の数が奇数本増える.
  • 連結成分同士を結ばないように辺を張る.

4つ目の場合はメモ化再帰でループが発生してしまいますが,実は $unused$ を偶数から奇数に移す場合は無視できます.
なぜなら,こういう操作をされた場合,次の手番の人が $unused$ を奇数から偶数に移せば,先ほどと同じ状態になるため,いずれは連結成分同士を結ぶ状況に陥るからです.(つまり偶数から奇数に移す操作が最善手であることはない.そういう状況はすでに負け確定.)
これでループが解消できたので,安心してかけます.

ソースコード

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

int dfs(int v, vector<string> const& g, vector<bool>& visited) {
    visited[v] = true;
    int res = 1;
    for(int i = 0; i < (int)g.size(); ++i) {
        if(g[v][i] == 'Y' && !visited[i]) {
            res += dfs(i, g, visited);
        }
    }
    return res;
}

int rec(int odd, int even, int unused, vector<vector<vector<int>>>& dp) {
    int& res = dp[odd][even][unused];
    if(res != -1) {
        return res;
    }

    if(odd + even == 2) {
        return res = unused;
    }
    if(unused == 1 && !rec(odd, even, !unused, dp)) {
        return res = 1;
    }
    if(odd > 0 && even > 0 && !rec(odd, even - 1, !unused, dp)) {
        return res = 1;
    }
    if(odd >= 2 && !rec(odd - 2, even + 1, unused, dp)) {
        return res = 1;
    }
    if(even >= 2 && !rec(odd, even - 1, !unused, dp)) {
        return res = 1;
    }
    return res = 0;
}

int main() {
    int N;
    cin >> N;
    vector<string> g(N);
    for(int i = 0; i < N; ++i) {
        cin >> g[i];
    }

    vector<bool> visited(N);
    int odd = 0, even = 0;
    int unused = 0;
    for(int i = 0; i < N; ++i) {
        if(!visited[i]) {
            int C = dfs(i, g, visited);
            unused += C * (C - 1) / 2;
            if(C & 1) {
                ++odd;
            } else {
                ++even;
            }
        }
        for(int j = i + 1; j < N; ++j) {
            unused -= (g[i][j] == 'Y');
        }
    }
    unused %= 2;

    vector<vector<vector<int>>> dp(N + 1, vector<vector<int>>(N + 1, vector<int>(2, -1)));
    if(rec(odd, even, unused, dp)) {
        cout << "Taro" << endl;
    } else {
        cout << "Hanako" << endl;
    }
}

感想

4つ目のパターンを書き忘れた状態で間違えて提出してしまったんですが,なぜか通ってしまい,ジャッジのケースが弱いのか,実は完全に無視して良いのかよくわからなくなった….
もしあるなら O(1) 解をもっと考えればそのうちわかるかも(考えませんけどね).

AOJ 2313 Box Witch

解法

ちゃんとフローがわかってるなら解ける問題.
まず辺の追加クエリは簡単で,単純に辺を増やすだけ.
問題は辺の削除クエリです.与えられた辺を $\{a, b\}$ とします.
今流れてるフローで与えられた辺が使われていないなら,単純に削除します(これは辺のキャパシティ $cap[u][v]$ を持っておいて,$cap[a][b] \neq 1$ であるかで判定できます.どっちが 0 かで流れている向きもわかる.)
使われている場合,残余グラフ上で $a \rightarrow b$ のパスが残っているなら,$a \rightarrow b$ のフローを1ながして $\{a, b\}$ を消せば,整合性を損なうことなく流量を維持できます.
もし $a \rightarrow b$ のパスがない場合,一旦 $n \rightarrow 1$ へのフローを1流し直して,そのあと $a \rightarrow b$ のフローを流すと,自然にもともとの $a \rightarrow b$ のフローを打ち消すことが出来ます.
あとは辺を消してフローを流し直すだけで終わります.

ソースコード

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

using graph = vector<vector<int>>;

int dfs(graph& g, vector<bool>& visited, vector<vector<int>>& cap, int v, int t) {
    if(v == t) {
        return 1;
    }
    visited[v] = true;
    for(auto to : g[v]) {
        if(visited[to] || cap[v][to] == 0) {
            continue;
        }
        if(dfs(g, visited, cap, to, t) == 1) {
            cap[to][v]++;
            cap[v][to]--;
            return 1;
        }
    }
    return 0;
}

int max_flow(graph& g, vector<vector<int>>& cap, int s, int t, int cnt = 100000) {
    vector<bool> visited(g.size());
    int f = 0;
    while(cnt--) {
        fill(visited.begin(), visited.end(), false);
        if(dfs(g, visited, cap, s, t) == 1) {
            f++;
        } else {
            break;
        }
    }
    return f;
}

int main() {
    int N, E, Q;
    cin >> N >> E >> Q;
    graph g(N);
    vector<vector<int>> cap(N, vector<int>(N));
    auto add_edge = [&](int from, int to) {
        g[from].push_back(to);
        g[to].push_back(from);
        cap[from][to] = cap[to][from] = 1;
    };
    for(int i = 0; i < E; ++i) {
        int f, t;
        cin >> f >> t;
        f--; t--;
        add_edge(f, t);
    }

    int res = max_flow(g, cap, 0, N - 1);
    while(Q--) {
        int m, a, b;
        cin >> m >> a >> b;
        a--; b--;
        if(m == 1) {
            add_edge(a, b);
        } else {
            // used b -> a
            if(cap[a][b] == 2) {
                // doesn't exist circuit b -> a on residual graph
                if(max_flow(g, cap, b, a, 1) == 0) {
                    max_flow(g, cap, N - 1, 0, 1);
                    max_flow(g, cap, b, a, 1);
                    res--;
                }
            } else if(cap[b][a] == 2) {
                if(max_flow(g, cap, a, b, 1) == 0) {
                    max_flow(g, cap, N - 1, 0, 1);
                    max_flow(g, cap, a, b, 1);
                    res--;
                }
            }

            cap[a][b] = cap[b][a] = 0;
            g[a].erase(find(g[a].begin(), g[a].end(), b));
            g[b].erase(find(g[b].begin(), g[b].end(), a));
        }

        res += max_flow(g, cap, 0, N - 1);
        cout << res << endl;
    }
}

感想

フローのいい練習になりそうな問題.