Eまで五完で終了。Fは誤読（というか、「連結」の定義を勘違い）でした。
コンテスト後のツイート
A for文使わないと書くの面倒じゃない？
— titia (@titia_til) April 16, 2022
B シミュレーション
C DP
D 各値のindexの配列を持って二分探索
E 全ての辺を列挙
F - Keep Connect
自力AC。
連結というのを、残した全ての辺同士が繋がっていれば良いと勘違いしたため解けず。その勘違いのせいで、DPの遷移が大変になったため時間が残せなかったというのも大きい。
正しい問題なら、最初に縦の線を取り除くかどうかを決めて、その後、コの字ごとに取り除くかを決めていくDPをするとすると、状態として最後の二点が連結かそうでないか、だけを持てば良いのですね。
それなら遷移の式も簡単でした。
G - GCD cost on the tree
解説放送を見てAC。
約数による（包）除原理を使うというのは典型だけれど、「xの倍数のみからなる長さの和」を木DP（DFS）でを求められるというのが気付きにくい。
解法も難しいけれど、TLEにならないよう実装するのが難し過ぎないですか？
解法通り実装したつもりが、よく考えると二乗になっている……みたいなことが多いし、二乗になっていなくても、dictとかを使っているとTLEになりやすい。
かなり苦労したけれど、setやdictを使いたくなるところで、できるだけ使わないようにしたらACできました。
0 件のコメント:
コメントを投稿