Eまで五完でした。
F - Make Pair
いかにも区間DPの問題だが、遷移が分からなかった。
コンテスト後、落ち着いて考えると、DP[x][y]について、「最後にlとr（x<=l<r<=y）を使ったとしたら……」と考えることで遷移できることに気付いた。しかし、これだと答えは合うが四乗になってTLE。
解説を見ると、x（DP[x][y]の左端）とペアになるものを探索することで遷移式が書ける、とあった。
解説を読めば確かに、という感じなのだけど、この遷移でいけるのは結構気付きにくい気がする。区間DPで三乗でいけるはず、というところから思いつく感じかなぁ。
G - Groups
コンテスト後、包除原理の方針で自力AC。
コンテスト中考えていた方針で大体合っていて、冷静になればどこが間違っていたか気付けた。これはコンテスト中に通せるべきだった。
……が、Fで時間を取られて冷静さを失っていたことが影響したと思う。この問題を反省するよりFを反省すべきか。
H - Snuketoon
解説放送や、maspyさんのslope trickに関する解説を読んでAC。
「プレイヤーが動く」と考えるのではなく、DPを考えて、そのDPテーブルの図形について考える（動かす）というのはちょっとした発想の転換か。
ただ、maspyさんが挙げている問題例を見ると、slope trickの問題ではこの見方は常套手段のよう。身に着けておきたい。
0 件のコメント:
コメントを投稿