Dまで四完。直後にGCJがあるため、あまり疲れないように取り組もうと思っていた。さらに、問題を開くと、やや眠くて頭が働いていないことが判明。そのため、GCJへのウォーミングアップのつもりでゆっくり問題に向かうことにした。
そのおかげ（？）か、このコンテストの順位はイマイチだったがGCJ Round2は通過できたので、作戦は成功。
D - Game in Momotetsu World
コンテスト中にACできたものの、かなり苦労した。
「ゴールからDP」という方針自体は結構早い段階で考えたのだけど、どういうDPをすれば良いか分からなくなってしまった。
・$DP[i][j]=(i, j)$からスタートしたときの自分$-$相手の最大値
とすれば上手くいく。
こういう「自分は利得を最大化し、相手は利得を最小化する」をミニマックス法というらしい。
E - Xor Distances
「木DP」「各bitごとに見る」といったキーワードが思い浮かぶが、実際に解くのはなかなか難しい。コンテスト中に大体の方針は立ったつもりでいたが、実際の解法とはややギャップがあった。
とはいえ、その二つのキーワードを思い付いたら、後は詰めていくだけ、という気もする。木DPの問題はいつも結構時間がかかってしまうのだけど、まあ慣れるしかないのかなぁ。
F - Insertion Sort
すぬけさんの解説放送を聞いてAC。
難しい。
・まず、一度も移動させない人たちを決める
というのが重要だけど、それを思い付くことすらなかなか難しいと思う。
その後は、
・平面にプロットして平面走査を考える
・DPをセグメント木を用いて高速化（セグメント木を使える形に変形するところも結構難しい）
という流れ。
こっちも難しくて、解説放送で方針を理解した後なのに大分実装に苦戦してしまった。
後半パートは確かに典型なんだけど、この典型をささっと処理するのは容易ではないと思う。
Codeforcesで何度か解いているはずだけど、毎回そこそこの時間がかかってしまっている。
0 件のコメント:
コメントを投稿