Dまで四完。
E - Swap
解説放送を見てAC。（解説方法後半の賢い方法で書いた）
制約を見ると全探索は無理そうなので、DPを疑ってはみたがどのような状態を持てばいいか全く分からなかった。
言われてみれば当たり前なのだけれど、何も思いつかないなら、「一文字目から決めていこう」と考えるべきでした。そうすれば、Swapがテーマなので転倒数が重要そうなのは分かるし、他に何をキーに持てばいいか、というと各文字の個数でしょう。
DPを疑い、「一文字目から決めていこう」とさえ思えれば、結構自然な考察で正しい解法にたどりつけたはず。Fを中心に考えていたとはいえ、何も思いつけなかったのは反省。
F - Treasure Hunting
解説放送を見てAC。（解説放送後半の、簡単かつ計算量の良い方法で書いた）
コンテスト中は嘘のDPに走ってしまったが、最初考えたときに二分探索（二文法）では？ と思ったときがあった。何を固定すれば良いか、どういう問題にすれば良いか分からず捨ててしまったけど、その着想が重要だった。
「K番目の数がX」となるときどうなるか？ という方針で上手くいくかどうかが分かりにくいが、この方針をちゃんと考えればDPに辿り着ける。
G - Divisors of Binomial Coefficient
ツイッターで「区間篩」というキーワードを見てAC。
EやFは難しかったと思うけど、この問題は解けなくてはいけなかった。反省。
H - Eat Them All
解説放送を見てAC。
・ハミルトン路（全ての頂点を一度ずつ通る閉路）を構築するより、オイラー路（全ての辺を一度ずつ通る閉路）を構築する方が簡単
これを使うのはなるほど。その後、
・グリッドが二部グラフであることを用いて、フロー（とその復元）を用いて各辺を通る回数を求める。
最後に、
・オイラー路の復元は、dfsの帰りがけでOK。
一つ目が見えても、二つ目三つ目のポイントを超えるのは難しい。ただ、フローがこういう風に使えるということを押さえておくのは頭に入れておきたい。
0 件のコメント:
コメントを投稿