Dまで四完で、時間もかかってしまった。
C - Not Equal
包除原理とかDPを疑ったため時間がかかった。
$C_i$が小さい順番に考えると分かりやすい、と気付けば難しくないが、他の解法も考えてしまいやすいのが難しい気がした。
D - Collision
LCAを使って解いてしまったが、使わなくても解けるというのは目から鱗。
E - Shiritori
グラフを作って後退解析ということは、（典型90問をやっていたこともあり）すぐ思いついた。
だが、その後の実装が難しい。
まず、開始位置が辺なのが問題を分かりにくくしている。勝ち負けの条件を逆にしてしまいやすい。
そして、メモ化再帰で実装しようとすると上手くいかず、後ろ向きにトポロジカルソートかSCCをしてその順番に見れば上手くのでは？ と考えたが、それでも上手くいかない。
すぬけさんの解説動画を見たが、各頂点について出次数を持っておいて、一つずつ減らしていく……というのは思いつきにくい。
さらに、一度見た頂点をもう一度見ないようにしないといけない、という辺りでも苦労した。多重辺が存在しうるため、二回見た方がいい気がしてしまうが、冷静に考えると見てはダメ。
最初に方針を立てるだけなら簡単だが、その方針を詰めるのも実装するのもかなり厳しい問題だった。
F - Deforestation
すぬけさんの解説動画を見てAC。
各木のコストの使用回数が1～3回になるため、コストが大きいやつを一回にして、その分をコストが小さいやつに回す（三回にする）……というようなことを考えて詰まった。
その方向性に見えてしまうと、隣同士に着目すれば良い、というのにはなかなか気付きにくい気がする。
その後の挿入DPも、解説を聞けばすんなり理解できるけど、自力で思いつけたかどうか。ただ、これは典型処理なので、前半の考察ができたなら解けなきゃまずい。
0 件のコメント:
コメントを投稿