ABDの三完。
Cが解けなかったのが響いて青に落ちてしまいました。最近レートは上がっていないとはいえ、そろそろ黄色は安定したかな……と思っていたのでショックが大きい。
C - Multiple Sequences
「最後の数字で場合分け」で解けます。
しかし、コンテスト後、そういうツイートを見た後でもしばらく考えこんでしまった。
たとえば、N=3で最後の数字が12なら、
・二倍する位置二つを１～3の中から選ぶ。
・三倍する位置を１～3の中から選ぶ。
とすると、得たい数列が一通りに定まります。
最初に問題を読んだとき、「倍数」という単語を見て、素因数分解はまず考えたはずなのですが、「最後の数字で場合分け」には思い至りませんでした。
その後は、N=1から順番に数字を決めていくというDPを高速化することばかり考えてしまいました。
（それでもできる気がしたけれど、やっぱりダメでした……というツイート）
E - Spread of Information
木DPだというツイートは見たけど、他は自力でAC。
コンテスト中は、問題を見て二分探索だろうとは思ったけど、「直径だけ調べていけないかな……」とだけ考えて、ダメなことを確認してCへ戻った。
直径だけではダメでも、木の端の方から置かなければいけないということは分かっていたので、そのまま考えていれば程なく木DP（か全方位木DP）でいけることには気付いたと思う。
ただ、木DPの実装にはあまり自信がない上DPの遷移もやや複雑なため、実装にかなり時間がかかってしまった。CをやらないでEに集中していたら通せてたか、というと厳しかったろうな。
F - Deque Game
解説放送を聞いてAC。
こういうゲーム問題では、相手の真似をする戦略が有効なことが多い。実際、数列が一つ（奇数長）で、最小値が中央にあれば、後手は先手と逆の方を取り除いていくのが最適になる。
そういう風に考えると、
・中央あたりの数字しか関係なさそう
・先手・後手が入れ替わるかが重要なので、数列の長さの偶奇が大切そう
といったあたりは思いつけると思う。（私は、ちょっとツイートなどを見てしまったので、ここまでも自力で思いつけたとは言えないけど……）
ただ、偶奇に着目しすぎると、
・実は、長さ2と長さ4で方針が異なる
ということに気付きにくくなると思う。これに気付き、さらに、
・長さ4以上で偶数の場合は、長さ3の場合二つのmin/maxへ帰着させられる
ことに気付くところが難しい問題だった。
言われてみれば自然なのだけど、私は解説動画を見るまで、長さ4のものをどう扱えばいいか分からなかった。
長さ4以上のものがないときは、ゲーム問題の典型手法で解けると思うし、ACした人ももっとたくさんいたと思う。さらにちょっと捻られたときに対応できるかが問われている気がした。
0 件のコメント:
コメントを投稿