B一完。CとDを考えたが分からず、Bだけ解いた。しかし、Cは解けなくてはいけない問題だった。
No.3513 Greedy Yokan Party
解法ツイートを見てAC。
答えで二分探索して、大きい方から二番目の長さがmid以上になるような、K個の分割があれば良いということは分かったが、その判定問題が解けなかった。
が、落ち着いて考えるとこれはDPで解ける。0/1/2回mid以上のものを取ったときのindexまででの最大分割数を配列として持てばOK。
DPで解けると言われればすぐに気付いたので、落ち着けば解けたはずの問題だった。
No.3514 Majority Driven Tree
解説AC。
木DPは考えたのだが、遷移の式などが上手く立てられず、全方位木DPが必要か？ などと考えてしまった。
DPテーブルを二つ用意すれば解けるというのはびっくり。「親が既に塗られていると仮定したときのコスト」を用意すると上手くいくとは気付けなかった。
二つDPテーブルを用意すると知った後なら、遷移を書くことは難しくなかった。
No.3515 Anti EIKO
解法ツイートで行列累乗を使うと知ってしまったけど、大体自力AC。
Kが小さいときはDPで求められることに気付けば難しくなかった。
これは自力で解けたはず、と思う。コンテスト中、最初にこの問題を開いたのに、ちゃんと考えずに違う問題に行ってしまったのは良くなかった。
0 件のコメント:
コメントを投稿