ABCDGの5完。Eに時間かけたうえ解けないのひどいね。昼間UTPCに出てたけど、そのときよりは調子が戻っていた。
A - Probably English
5回コピペ。これより早く書ける実装はそうないだろ。A問題は、単語5つじゃなくて単語1つが妥当だと思う。
B - Bombs
爆発範囲だけを探索しようとすると(実装したくなさすぎて)固まってしまうけど、それぞれの壁視点で爆弾を全探索して範囲に入っているかを確認するという方針に気づいて解けた。4重ループ。思いつくのがかなり難しい全探索。
言われてみれば、爆弾視点でマスを全探索しても同じだった。いや本当に難しい。考察というよりは実装テクかな(その意味では有用な典型)。そういえば最初は100*100くらいの配列を確保してたよ(爆発範囲がはみ出してもいいように)。
C - Socks
mapで数えてもいいんだけど、普通にソートしてペアを作っていっても実装は簡単。
D - Three Days Ago
区間の開始地点を固定しても長さを固定してもまとめて数えられるようには思えない。Dで解ける気がしないのは稀。とりあえずおしっこしてきた。
累積和の差が0になればってやつかあ。文字が10種類もあって2の倍数かどうかという話だったから、思いつかなかった。気づけば簡単で、偶奇情報の累積を10bitでN+1個持って、まあソートしてランレングスとかで。
E - Kth Number
パッと見で何を言っているのかさっぱりわからない。頑張って読むと、各jに対してA_K=jとなる確率を求める方針くらいしかなさそうだと思う。あまり考えたくないやつだが頑張って考えると、(0-indexedで)j未満がK個以下かつjより大きいのがN-K-1個以下になる確率。3乗になってしまうが、とりあえず書くか?ソートではなく何が何個あるかを累積和の形で持つほうがよさそう。混乱している。30分やってようやく解けないと気づき他の問題を見ることに。
Gを通したあと、考えを整理して3乗を実装したが、サンプル通らず。
F - substr = S
どの位置で合致するかというのを全探索できそう。桁DPみたいで、脳を破壊され時間を消費しそう。Eで時間を使ってしまったので、こんなことをやっている時間はない。あまり考えずに飛ばした。
G - Minimum Reachable City
UTPCのOでUnionFindを使ったので見えやすかった。最初のグラフは要するに木(有向辺が親から子へ張られている)。クエリで追加されるのは、祖先への有向辺。追加されるとループができるが、それによってループ内の頂点間は自由に行き来できるようになる(当たり前ではあるけど、行き来できるという同値関係に気づくことでUnionFindが使える)。木なので祖先までは一本道。分岐してても変な重なり方しててもUnionFindでOK。親を辿って全部mergeする計算量は、UnionFindで最小の頂点番号も持っておけばそこへジャンプできて、処理した回数とmerge回数が同じオーダーでmerge回数がO(N)なので気持ちいいね。実装しながら少しずつ理解していく感じだった。