AOJ 1169 : 最強の呪文 (The Most Powerful Spell)

接頭辞の長さごとに、辞書順最小となるものを求めるようなダイクストラ法。ゴールへの経路は、もし閉路を含まなければN個以下の頂点からなるはずで、接頭辞の長さの最大値は6*(N-1)

これより長い接頭辞で、辞書順がさらに小さいような経路があれば、その呪文は閉路を含んでいるはずであり、辞書順がより小さい呪文を作れるのでNOを出力。そもそも経路がない場合も。

そうでなければ辞書順最小の呪文を出力。

AOJ 1330 : Never Wait for Weights

int N, M, INF = 10000000, vis[100001], dis[100001], U[100001], V[100001];
vector<pii> G[100001];

void solve() {
    rep(i, N)G[i].clear(), vis[i] = 0;
    // Union-Find木
    UnionFind uf(N);
    // クエリの種類
    // 0: 返答可能な質問
    // INF: 返答不可能な質問
    // -INF: 質問ではない
    vi knd(M);
    rep(i, M) {
        int u, v;
        char s[2];
        // 入出力が多そうなのでcin/cout系は使わない
        scanf("%s%d%d", s, &u, &v);
        char c = s[0];
        --u; --v;
        /*
        Union-Find木で2頂点で連結成分を管理。重さwの辺(u, v)と重さ-wの辺(v, u)を張っていく。
        閉路ができる場合があるが、無視する。というのは、重さの設定に矛盾がないので、必ずパス(u, v)の間の距離が一定であるため。
        つまり、こうして辺を張っていくと幾つかの森ができている。
        */
        if (c == '!') {
            int w; scanf("%d", &w);
            // 連結成分が異なるなら
            if (uf.find(u) != uf.find(v)) {
                G[u].emplace_back(v, w);
                G[v].emplace_back(u, -w);
                // 同じ連結成分になった
                uf.unite(u, v);
            }
            knd[i] = -INF;
        } else {
            /*
            連結成分が異なるので、重さの比較ができない。
            */
            if (uf.find(u) != uf.find(v)) {
                knd[i] = INF;
            } else {
                /*
                同じ連結成分に含まれるので、重さの比較ができる。
                */
                U[i] = u; V[i] = v;
            }
        }
    }
    /*
    今、グラフは森になっている。各連結成分、つまり木を根つき木として考える。
    u→vの距離
    = (根→vの距離) - (根→uの距離)
    が成り立つ。
    よって、事前に各連結成分について根を定めて根からの距離を求めておけばよい。
    */
    rep(i, N)if (!vis[i]) {
        stack<tuple<int, int, int> > stk;
        stk.push(mt(i, -1, 0));
        while (sz(stk)) {
            int u, p, d;
            tie(u, p, d) = stk.top(); stk.pop();
            vis[u] = 1;
            dis[u] = d;
            each(e, G[u])if (e.first != p)stk.push(mt(e.first, u, d + e.second));
        }
    }

    rep(i, M) {
        if (knd[i] == INF)puts("UNKNOWN");
        else if (knd[i] != -INF)printf("%d\n", dis[V[i]] - dis[U[i]]);
    }

}

int main(){
    while (scanf("%d%d", &N, &M), N) {
        solve();
    }
}

AtCoder AGC 014 B: Unplanned Queries

性質を満たす木が存在する必要十分条件は、すべての頂点についてクエリに現れた回数が偶数であることである。

(1)すべて偶数回の出現だった場合

すべてのクエリについて

辺(a[i], b[i])で2頂点をつなぐ。ただし、a[i], b[i]がすでに同じ連結成分内にある場合はこのクエリを無視。

最終的にできた森から適当に木を作れば、性質を満たしている。

(2)奇数回現れる頂点がある場合

根付き木を考える。

mod 2のもとで

クエリ(u, v)は

(u, root), (v, root)

に分解できる。

奇数回現れる頂点のうち最も深いもの1つを頂点uとする。

頂点uを端点とするパスによってuとその親pをむすぶ辺(u, p)は奇数になっている。辺(u, p)の数を偶数にしたい。

そのために、uの子孫のうちuを除く頂点(その集合をSとする)の出現回数が合計で奇数でなければならない。しかし、そうなると奇数回現れる頂点でuより深いものが存在することになり矛盾する。よって、辺(u, p)の数は奇数になる。

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で解が求まる。