AtCoder AGC 014 C: Closed Rooms

k回目の魔法で部屋を開いた状態にする操作は、k+1回目以降の移動にしか影響しない。

よって、魔法を以下のように捉え直す。

1回目の魔法は移動のみ

2回目の魔法は部屋を開く操作ののち、移動

2回目以降の操作はK個以下の部屋を開き、K個以下のマスを移動できるので、出口へまっすぐ進めばいい。よって1回目の移動でどのマスへ行けるかを探索で調べる。到達できた各マスについて、到達可能なマス(x, y)から外へ通じるマスまでの距離をd(x, y) とした時

min(ceil(d(x, y)/K)+1)

が解。

AtCoder AGC 014 D: Black and White Tree 

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    int N;
    cin >> N;
    vector<set<int> > G(N);
    rep(i, N - 1) {
        int a, b;
        cin >> a >> b;
        --a;
        --b;
        G[a].insert(b);
        G[b].insert(a);
    }

    /*
    完全マッチングが存在するか判定
    木なので、葉は必ずその親とペアになる。葉から貪欲にペアを作っていく。
    */
    // 頂点vを取り除いた, 頂点vは葉への辺をもつ。
    vi rem(N), lev(N);
    queue<int> q;
    rep(i, N)if (sz(G[i]) == 1)lev[*G[i].begin()] = 1;
    rep(i, N)if (lev[i])q.push(i);

    while (sz(q)) {
        int u = q.front(), flag=0; q.pop();
        // uは葉vと辺(u, v)でつながっている
        each(v, G[u]) {
            if (sz(G[v]) == 1 && !flag++) {
                // vは葉なので黒く塗る
                rem[v] = 1;
            }
            G[v].erase(u);
            if (sz(G[v]) == 1) {
                // 辺を減らすことで、頂点vが葉になった。
                int w = *G[v].begin();
                q.push(w);
            }
        }
        // uを白に塗る
        rem[u] = 1;
    }

    /* 
    完全マッチングが存在しなかった。
    完全マッチングが存在しない木を
    根付き木として考えて
    最も深い葉で共通の頂点を親として持つものがあるならば、その親を白く塗れば先手の勝ち。(1)
    そうでない場合は、この2頂点を取り除く。その木にも当然完全マッチングが存在せず、よりサイズの小さい問題になった。
    これを繰り返すと(1)に至るかまたは頂点数が1になるって先手の番になる。どちらも先手の勝ち。
    */
    rep(i, N)if (!rem[i] && sz(G[i]) == 0) {
        cout << "First" << endl;
        return 0;
    }
    // 完全マッチングが存在した
    // その場合、先手に対して後手は完全マッチングでペアになる頂点を選べばいい。
    cout << "Second" << endl;
}

yukicoder #515: 典型LCP

事前に文字列を辞書順にソートしておく。
l番目の文字列とr番目の文字列のLCPをlcp(l, r)のように表すことにする。
|lcp(l, r)| <= |lcp(l+1, r)|
が成り立つから
lcp(l, r)
= lcp(lcp(l, l+1), lcp(l+1, r))
よって、長さx以下のprefixについて、lcp(i, j)を求める問題をlcp(x, i, j)とすると、各クエリは(∞, l, r)のように表せて
(∞, l, r)
= (|lcp(l, l+1)|, l+1, r)
= (min(|lcp(l, l+1)|, |lcp(l+1,l+2)|), l+2, r)
= ...
= (min[l<=i<=r-1](lcp(i, i+1)), r, r)
したがって、事前に隣接する文字列のLCP、lcp(i, i+1)をすべて求めておけば、RMQで解が求まる。

Expected diameter of a tree | Codeforces #411

コメントつきコード

// 頂点の数、辺の数、連結成分のID、最も遠い点までの距離、連結成分の直径
int N, M, Q, cmp[100001], far[100001], nc, dia[100001];
// グラフ、連結成分ごとに最も遠い点までの距離をすべてもってソートしたもの
vi G[100001], F[100001];
// その部分和
vll S[100001];
// メモ
map<pii, ll> DS;

int bfs(int root, int c) {
    queue<tuple<int,int,int> > q;
    q.push({ root,-1, 0});
    int ma = -1, fa = 0;
    while (sz(q)) {
        int u, p, d;
        tie(u, p, d) = q.top();
        q.pop();
        cmp[u] = c;
        if (d > ma) {
            fa = u;
            ma = d;
        }
        /*
        頂点uから最も遠い点までの距離を求める。
        */
        smax(far[u], d);
        each(v, G[u])if (v != p) {
            q.push({ v,u,d + 1 });
        }
    }
    return fa;
}

ll solve(int U, int V) {
    if (DS.count({ U,V }))return DS[{U, V}];
    int madi = max(dia[U], dia[V]);
    ll &res = DS[{U, V}];
    /*
    ここの最悪ケースを考えてみよう。
    すべての連結成分の大きさが√nのとき
    √n個のUについてxは√N個あり、相手のVがc√N個
    中で二部探索しているので
    O(n^(3/2)log(n))
    **/
    each(x, F[U]) {
        /*
        madi > x + y
        連結しても直径はmadiのまま
        madi <= x + yのとき
        連結すると直径は
        x + y + 1
        y ∈ F[V]
        最小のyを求める
        madi - x <= y
        */
        int k = (int)distance(F[V].begin(), lower_bound(all(F[V]), madi - x));
        res += (ll)k*madi;
        // madi<=x+y
        // x+y+1のx+1の部分を足す
        res += (ll)(x + 1)*(sz(F[V]) - k);
        // x+y+1のyを足す
        res += S[V].back() - S[V][k];
    }
    return res;
}

int main(){
    cin >> N >> M >> Q;
    rep(i, M) {
        int u, v;
        scanf("%d%d", &u, &v);
        --u; --v;
        G[u].push_back(v);
        G[v].push_back(u);
    }
    MEM(cmp, -1);

    /*
    各木について直径を求める。
    また、頂点vから最も遠い点までの距離をすべて求める。
    */
    rep(i, N) if (cmp[i] == -1) {
        // iから最も遠い頂点はx
        int x = bfs(i, nc);
        // xから最も遠い頂点はy
        int y = bfs(x, nc);
        // (x, y)の距離が直径
        dia[nc] = far[y];
        // 任意の頂点についてxまたはyが最も遠い頂点の1つである。
        bfs(y, nc);
        nc++;
    }
    
    /*
    最も遠い点までの距離たちを連結成分ごとにまとめてからソートする
    */
    rep(i, N)F[cmp[i]].push_back(far[i]);
    rep(i, nc) {
        sort(all(F[i]));
        S[i].resize(sz(F[i]) + 1);
        rep(j, sz(F[i])) {
            S[i][j + 1] = F[i][j] + S[i][j];
        }
    }

    while (Q--) {
        int u, v;
        scanf("%d%d", &u, &v);
        --u;
        --v;
        int U = cmp[u], V = cmp[v];
        if (U == V) {
            printf("%d\n", -1);
            continue;
        }
        if (sz(F[U]) > sz(F[V]))swap(U, V);
        ll x = solve(U, V);
        double ans = (double)x / sz(F[U]) / sz(F[V]);
        printf("%0.10f\n", ans);
    }
}

Find Amir | Codeforces #411

2番目の入力例n=10を考えてみよう。

とりあえず、(i+j) mod (n+1) = 0

となるような辺(i, j)はコスト0なので全部張ろう。

1-10

2-9

3-8

4-7

5-6

あとはコスト1以上の辺を貼るしかない。

実はすべてコスト1の辺で繋げられる。

10+2≡1

9+3≡1

8+4≡1

7+5≡1

よってコストは4。

奇数の場合も同様に考えることができる。したがって解は

floor((n-1)/2)

 

クラスカル法っぽくやる

Minimum number of steps | Codeforces #411 (Div. 1)

abのような形が残らないので、操作していくと最終的に

bbb....baa...a

のような形になる。

とりあえず実験してみる。

ab

→bba

bはaを飛び越えるときに1個から2個になった。

abに対する操作は1回。

aab

→a<ab>

→abba

→<ab>ba

→bbaba

→bb<ab>a

→bbbbaa

aを2個飛び越えることでbは4個になった。

abに対する操作は1+2回。

...

k>=1のとき

(aがk個)b→(bが2^k個)(aがk個)

abに対する操作は1+2+...+2^(k-1) 回

 

あとは、すべてのbについて、そのbより左にあるaを数えて、この操作回数の和を求めればいい。