コンテスト後のツイート
最初TLEしたときdefaultdictのせいかと嫌な気持ちになったが、ただのmodの取り忘れでほっとした。
— titia (@titia_til) June 21, 2025
F マージテクだよね→WA。WAの原因が分からぬまま終了。愚直を書くべきだったかも。
F - Contraction
自力AC。
コンテスト後の冷静な状態ならすぐ分かるだろうと愚直書かずにやろうとしたらペナ量産。一時間くらいして諦めて愚直＆ランダムテストを書いたらようやく分かってAC。消すべき辺を消していないところがあったためのWA（やRE）でした。
愚直を書いた方が速く解ける場面が多いのはそうだけど、これくらいの問題で愚直を書くのも……という気持ちも間違ってないと思うので、どうしたら良いのかね。
G - Count Cycles
一応自力ACだが、bit DPでいける……みたいなツイートは目にしていた。
素直にbit DPを書くとN^3 * 2^Nくらいの計算量になるが、定数倍高速化をしていればなぜか通る。ただし、自分の場合はPyPyでは通らず、RUSTに直さなくてはいけなかった。
が、これは、start位置を固定してそれぞれでbit DPを行っていると考えられるためで、そう考えると実は（ならし）計算量が減っている（解説を見て理解）。
その方針ならPyPyでもACできた。
0 件のコメント:
コメントを投稿