Fまで六完。
コンテスト後のツイート
F 子だけでコストを使い果たしているかどうか場合分けして木DP
— titia (@titia_til) July 9, 2022
G 問題を見て、フローだ！ と思ったのにグラフが構築できず終了。うーん。
G - Grid Card Game
解説AC。（解説放送も見た）
コンテスト中、いわゆる「燃やす埋める問題」ではないかと疑ったりもしたのだが、違うと思ってしまった。
・start→行のノードたち→列のノードたち→ゴール
みたいなグラフを考えていたのだけど、
・start→行および列のノードたち→ゴール
を考えるのが正解。「燃やす埋める問題」を思ったなら、そういうグラフを考えるのは当然なはずなのに、捨ててしまったのはまずい。
こういうグラフ構築と、「燃やす埋める問題」では「Xを選択してYを選択しない場合のペナルティ」を見ていく、という点は頭に入れておきたい。
その後の処理もテクニカルだけど、この系統の問題になれていれば突飛な考え方ではない気がする。類題経験を積んだ方が良さそう。
Ex - Yet Another Path Counting
解説放送を見てAC。
二通りの四乗の解法がある：
・同じラベルの二点全てについて二項係数を足す
・多点スタートのDPをする
各ラベルの個数によりこれらを使い分けることで三乗になり、ACできる。
コンテスト中は一番目の方法しか思いつけなかった。二つ目も見たことあったのに。
0 件のコメント:
コメントを投稿