Dまで四完でした。EFを見てFに行ったのですが、解けずに終了。Eの制約には気付いていたのに、やり方を思いつかなかったのも、Fの解法が思いつかず迷走してしまったのも大いに反省です……。
E - Oversleeping
コンテスト中は主にFを考えていたので、こちらはあまり考えなかったのですが、Y,Qの制約が小さいのには気付いていました。しかし、周期性があるのなら、制約が小さくても何の意味があるんだろう？ と思い、全探索を思いつかず。
Y, Qを固定した場合の式を立式していれば解法に気付けたんでしょうか……。中国剰余定理まわりにもやや苦手意識があるので、ちょっと自信がないです。
・制約が小さいのだから、Y, Qを固定、全探索を考える
・Y, Qが決まっている場合を立式し、中国剰余定理に帰着
のどちらのステップも自然な考察でたどりつけるものなので、できなかったのはまずいですね。反省。
F - Zebraness
フロー。
いわゆる「Project Selection Problem」（燃やす埋める問題）だった。
フローと疑えば気付けるかもしれないけど、結構難しいですね。
なお、PyPyだと（自分の）Ford-Fulkersonだと間に合わず、初めてDinic法を実装した。挑戦したことはあったけど理解できなくて今まで避けていたもの。とはいえ、分かってしまえばそこまで複雑ではなかったですね。
0 件のコメント:
コメントを投稿