Cまで三完。Cで苦戦してしまったが、レートはそこまで落とさずに済んだ。
C - Odd Even Sort
三文字以下なら、交互に操作し続けることでソートになる、というのは気付かなければいけないけれども、後は大きい数字を右に移動させていくだけで良い。そうすると、自然に規定回数以下に収まる。
後は実装問題なので何を反省すべきかね……。
とりあえず、WAやTLEがでたときにすぐにcheckerを書いて（結局、何回かペナを出した後で書いた）いれば、ペナルティ量産は防げたと思う。
D - 1 or 2
解説AC。
ツイッターなどでヒントを見ていたのでどこまで自力かは分からないけど、常に二つ選ぶなら、ソートして大きい方と小さい方から取っていくのが最適、というのは気付いた。
あとは、一個だけで取るものをどう選ぶかだけど、ソートしたものの中である区間になっているはず。その区間全探索を普通にやると三乗だけど、何か差分計算とかで高速化するのかなぁ……とか考えながら解説を見たら、思った以上にシンプルでした。
なお、解法ツイートを見ると、（高速化は分からないけれど）正負などで場合分けして一個取る場所の範囲を絞れば通るみたいですね。
E - Directed Tree
解説AC。
……といっても、公式解説を読んだだけではなかなか理解できず苦労してしまった。
木の問題で、木DPをするのでは？（制約を見ると、二乗の木DPかも？） 使ってはいけない数字が指定されるので、包除原理を使うかも？ といったあたりは考えた。が、そこで詰まってしまった。
キーワードはこの問題と共通ですね。そして、今回の問題はこの問題よりDPを立式するのは簡単なはず。とはいえ、なかなか立式するのは難しい気がする。
結論からいうと、解説の通り、
・$DP[i][j]$を$i$を根とする部分木に$j$箇所条件に違反するように書き込む方法の個数
とするのだけれど、この「部分木」というのは、その部分木の祖先がどうなっているのか、とかとは全く関係ない、本当にただの部分木です。その部分木に関する入力が与えられたら、その答えを求めるものです。
……いや、素直に解説を読めばそう（だし、二乗の木DPを使う問題ではそういう風に置くものなのかも）なんですが、私は、祖先のノードが何個あるから禁止すべき個数は……などと考えてしまいました。
それだと遷移が上手くいかなくて、ただの部分木に関する問題のDPテーブルが求まっていたら遷移が上手くいく、というのは不思議です。
あと、この問題の難しさは、包除原理を使うなら、$DP[i][j]$の$j$は必要なさそうなのに、$j$を明示的にしなくてはいけない、という部分だと思います。最終的に、$j%2$によって足すが引くかを決めるので、$DP[i][2]$で良いのでは、と思ってしまいそう。
ただ、$DP[i][j]$の$j$があっても二乗に収まる、というのが二乗の木DPなので、二乗の木DPを使おうという気持ちで臨むとDPの立式もしやすいのかもしれない。
どうDPテーブルを置くかが難しい問題な気がしたけど、二乗の木DPに慣れていれば分かるのかも？ とも思えてきました。
練習すれば、DPの置き方も含めて典型と思えるようになるのかな……。
（FはACした後書くつもり。）
0 件のコメント:
コメントを投稿