C. Kuro and Walking Route | Codeforces Round #482 (Div. 2)

/**
Flowrisa から Beetopiaへのパスの辺を
取り除いたグラフを考えよう。このグラフは少なくとも2つの部分木からなり、
1つはFlowrisaを含み、もうひとつはBeetopiaを含む。
もとのグラフにおいてFlowrisaを含む部分木からBeetopiaを含む部分木
への経路だけが不正な経路なのでそれを全体から除く。
**/

int N, X, Y;
vi G[300005];

// 部分木の頂点数を数える
int dfs(int u, int p, int ng) {
    if (u == ng)RT 0;
    int re = 1;
    each(v, G[u]) if(v!=p){
        int a = dfs(v, u, ng);
        // Flowrisaから見てBeetopiaへのパスだった
        // またはBeetopiaから見てFlowrisaへのパスだった
        if (a == 0 && u != (X^Y^ng)) {
            RT 0;
        }
        re += a;
    }
    RT re;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout << fixed << setprecision(20);

    cin >> N >> X >> Y;
    --X; --Y;
    rep(a, N - 1) {
        int u, v;
        cin >> u >> v;
        --u; --v;
        G[u].push_back(v);
        G[v].push_back(u);
    }

    // Flowrisaを含む部分木の頂点数
    ll xx = dfs(X, -1, Y);
    // Beetopiaを含む部分木の頂点数
    ll yy = dfs(Y, -1, X);
    // (全体)-(Flowrisa->Beetopiaを含む経路)
    ll re = N*(N - 1ll) - xx*yy;
    cout << re << endl;
}

B. Treasure Hunt | Codeforces Round #482 (Div. 2)

const string ALPHA = "abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ";
string NAME[3] = { "Kuro", "Shiro", "Katie" };

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout << fixed << setprecision(20);
    ll N; // 0<=N<=10^9
    cin >> N;
    vector<string> S(3);
    vll ma(3);
    rep(a, 3) {
        cin >> S[a];
        // 1文字のsubribbonだけ考えればいい。
        // すべての1文字のsubribbonを試す
        for (char b : ALPHA) {
            ll x = 0;
            each(c, S[a]) {
                if (b == c)x++;
            }

            // 全部の文字をbにしてもターンが余る場合
            if (N > sz(S[a]) - x) {
                // 余分にpターンある
                ll p = N - sz(S[a]) + x;
                // N = p = 1かつS=bbb...bbbの場合
                // 1つだけ異なる文字になる
                // pが偶数のときは、ある箇所を別の文字にして戻すのをp/2回繰り返せばいい。
                // 上記以外でpが奇数の場合は
                // 全部をbにする直前の操作で
                // 別の文字u=>別の文字v=>b
                // と操作することで残りのターン数が偶数になるので可
                if(p==1 && x == sz(S[a])) smax(ma[a], sz(S[a]) - p);
                else smax(ma[a], (ll)sz(S[a]));
            } else {
                // 他の文字をひたすらbに変えていくだけ
                smax(ma[a], N + x);
            }
        }
    }

    ll m = -1, cnt = 0, cat=-1;
    rep(a, 3) {
        if (m < ma[a]) {
            cat = a;
            m = ma[a];
        }
    }
    rep(a, 3)if (m == ma[a])cnt++;
    if (cnt > 1)cout << "Draw" << endl;
    else cout << NAME[cat] << endl;
}

F - Monochrome Cat | AtCoder Regular Contest 097

公式解説みて書いた

void dfs(int u, int p, int d, vector<vi> &H, vi &dist, vi &score) {
    dist[u] = d + score[u];
    each(v, H[u])if (v != p) {
        dfs(v, u, dist[u], H, dist, score);
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout << fixed << setprecision(20);

    int N;
    cin >> N;
    vector<vi> G(N);
    rep(a, N - 1) {
        int x, y;
        cin >> x >> y;
        --x; --y;
        G[x].push_back(y);
        G[y].push_back(x);
    }

    string A;
    cin >> A;
    vi C(N);
    int nw = 0;
    rep(a, N) {
        char c = A[a];
        C[a] = c == 'W' ? 1 : 0;
        nw += C[a];
    }

    if (nw <= 1) {
        cout << nw << endl;
        return 0;
    }

    vi deg(N);
    queue<int> Q;
    rep(a, N) {
        deg[a] = sz(G[a]);
        if (deg[a]==1 && !C[a]) {
            Q.push(a);
        }
    }
    vector<bool> removed(N);
    while (sz(Q)) {
        int u = Q.front();
        removed[u] = true;
        Q.pop();
        each(v, G[u]) {
            if (--deg[v] == 1 && !C[v]) {
                Q.push(v);
            }
        }
    }

    fill(all(deg), 0);
    vector<vi> H(N);
    int V = 0;
    rep(u, N)if (!removed[u]) {
        V++;
        each(v, G[u])if (!removed[v]) {
            H[u].push_back(v);
            deg[u]++;
        }
    }

    // Euler Tourした場合のコスト
    // すべての頂点は(次数)回ずつ値変更
    int re = 2 * (V - 1), S = 0;
    vi score(N);
    rep(a, N) if(!removed[a]){
        int x = C[a] ^ (deg[a] & 1);
        re += x;
        score[a] = x;
        if(deg[a]==1)S = a;
    }

    // すべての頂点を訪れたらEuler Tourを打ち切る。
    // 残りのパス上の頂点は(次数-1)回ずつ値変更
    
    // 一番コストを減らせるパスを探す
    // 木の直径を求めるのと同じ
    vi dist(N);
    dfs(S, -1, 0, H, dist, score);
    rep(a, N)if (!removed[a]) {
        if (dist[S] < dist[a] && deg[a] == 1)S = a;
    }
    dfs(S, -1, 0, H, dist, score);
    int ma = 0;
    rep(a, N)if (!removed[a]) smax(ma, dist[a]);
    re -= 2*ma;
    cout << re << endl;
}

D - Equals | AtCoder Regular Contest 097

(x[j], y[j])を辺とするようなグラフを考える。このグラフの各連結成分内では要素は各辺を介したスワップによって自由に配置できる。よって頂点iを含む連結成分にp[i]が含まれるかを調べればいい。連結成分の識別にはUnion Find木を使うと便利。

int N, M;
vi P(N);
rep(i, N) {
    cin >> P[i];
    --P[i];
}
UnionFind uf(N);
vi X(M), Y(M);
rep(i, M) {
    cin >> X[i] >> Y[i];
    --X[i];
    --Y[i];
    uf.unite(X[i], Y[i]);
}
int re = 0;
rep(i, N) if (uf[i] == uf[P[i]]) re++;
cout << re << endl;

C - K-th Substring | AtCoder Regular Contest 097

priority queueに(s[i,i], i), 1<=i<=Nを挿入していく。あとは先頭の要素をとってきて右端を1個伸ばしたものをpriority queueに挿入していく。ダイクストラ法で辺によって隣接する頂点を追加するのに似ている。s[l, r] <= s[l, r+1]なのでs[l, r]が取り出されたのよりも後にs[l, r+1]が取り出されるので正しい。異なる部分文字列をK個調べたら終了。

string S;
cin >> S;
int K;
cin >> K;
const int N = sz(S);
using P = pair<string, int>;
priority_queue<P,vector<P>,greater<P> > T;
rep(i, N) {
    string s;
    s += S[i];
    T.push(mp(s, i));
}

string re = "";
rep(i, K) {
    auto p = T.top(); T.pop();
    int j = p.second + sz(p.first);
    if (re == p.first) {
        --i;
    }
    re = p.first;
    if (j < N) {
        p.first += S[j];
        T.push(p);
    }
}
cout << re << endl;

E - Sorted and Sorted | AtCoder Regular Contest 097

隣接要素同士の交換しかできないのだから、もし白または黒のみであれば、最小の操作回数は転倒数に等しい。

この問題では、白と黒の２色の並び方ごとに操作回数が異なる。しかし、白と黒の並びが定まれば、操作回数は一意に定まる。なぜなら、各並び方について、白黒区別なく先頭から1~2Nと番号をつけ直せば、ただの順列のソートであるため。

先頭の要素からソートしていく。

dp[w][b]:=「先頭へ詰めて白1~w, 黒1~bをソート済みのときの最小の操作回数」

とおく。先頭からw+b個はソート済みということ。 このとき、次に白、黒のどちらがきても dp[w+1][b]またはdp[w][b+1]のどちらかを更新することで対応できる。dp[N][N]が解。

状態(w, b)で次に白または黒をw+b+1番目まで持ってくるときのコストを知る必要がある。対称性から、次に白が来る場合だけを考える（黒の場合も同様）。w=b=0のとき、白1番がk番目にあるとすると、コストk-1で先頭まで持って来れる。状態から(w, b)の場合は、kより左にあってソート済みの要素を超えて左に行く必要がないのでコストはkより左にあってソート済みでない要素の個数。左にあってソート済みでない要素の個数はBinary Indexed TreeでDPのループごとに計算できる。

template<class Val>
struct BinaryIndexedTree {
    int n;
    vector<Val> t;
    BinaryIndexedTree() {}
    BinaryIndexedTree(int _n) :n(_n + 1), t(_n + 1) {}
    void add(int k, Val val) {
        k++;
        while (k < n) {
            t[k] += val;
            k += (k&-k);
        }
    }
    void set(int k, Val val) {
        add(k, -sum(k, k + 1));
        add(k, val);
    }
    Val sum(int k) {
        Val r = 0;
        while (k > 0) {
            r += t[k];
            k -= (k&-k);
        }
        return r;
    }
    Val sum(int l, int r) {
        return sum(r) - sum(l);
    }
};
typedef BinaryIndexedTree<int> BIT;

const ll INF = 1ll << 60;
ll dp[2001][2001];

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout << fixed << setprecision(20);

    int N;
    cin >> N;
    vector<char> C(2*N);
    vi A(2*N), wk(N), bk(N);
    rep(i, 2*N) {
        cin >> C[i] >> A[i];
        --A[i];
        if (C[i] == 'W')wk[A[i]] = i;
        else bk[A[i]] = i;
    }

    rep(i, N + 1)rep(j, N + 1)dp[i][j] = INF;
    dp[0][0] = 0;
    BIT bit(2 * N);
    rep(i, 2 * N)bit.add(i, 1);

    rep(w, N+1) {
        rep(b, N+1) {
            if (w < N) {
                ll x = bit.sum(wk[w]);
                smin(dp[w + 1][b], dp[w][b] + x);
            }
            if (b < N) {
                ll x = bit.sum(bk[b]);
                smin(dp[w][b + 1], dp[w][b] + x);
            }
            if (b < N)bit.add(bk[b], -1);
        }
        rep(b, N)bit.add(bk[b], 1);
        if(w<N)bit.add(wk[w], -1);
    }

    cout << dp[N][N] << endl;
}

B: Find Symmetries | AtCoder Grand Contest 023

よい盤面である条件は、1<=i<=Nについてi行目とi列目が等しいことと同値。例えばN=4については、以下が等しければよい。 更にこの図から、任意の自然数の組(A, B)について(A+x, B+x) (xは自然数) も(A,B)と比較対象が同じであることがわかる。たとえば、(A, B) => (A+1, B+1)において比較する行と列がすべて右下にずれる（ただし下端、右端は循環）。よって、各A-B=Cについて(C, 1) をチェックする。この可否は(C, x) (1<=C<=N)と等しいのでN回だけチェックすればいい。１回のチェックはO(N²)かかり、全体でO(N³)の時間で間に合う。

公式解説の実装

int N, re = 0;
cin >> N;
vector<string> S(N);
rep(a, N)cin >> S[a];
rep(a, N) {
    re += [&] {
        rep(x, N)rep(y, N)
            if (S[(x + a) % N][y] != S[(y + a) % N][x])RT 0;
        RT N;
    }();
}
cout << re << endl;

思いつき方？

計算量多すぎ＝＞どこをまとめて計算する？＝＞盤面を分類

だめな別解（ローリングハッシュ）