ABCDFの五完。なんとかFを解けて良かった。
コンテスト後のツイート
E 予めS_Nの長さを求めて、[l,r]のrに近い最も大きいindexを使って、再帰で小さい方へ帰着できると思ったがTLE&REが出てダメ。
— titia (@titia_til) March 21, 2026
F 遅延セグ木DP。戻って良いという条件のもと、1からNへ辿り着く方法を求めたい。スタート地点を2^Mとし、x→yが来たら、[x,y]を半分にし、yにその分を加算。DP[N]が答え。
E - Fibonacci String
コンテスト中のコードを修正してAC。
コンテスト中に見逃していたのは、[L,R]の文字の個数は[0,R]の範囲のものから[0,L-1]のものを引いて求められるということだった。基本的なことだけれどなぜか忘れて最後まで気付けなかった。
[L,R]のまま扱おうとしたことでlが大きい場合にREになるコードになっていたのも本質的にまずい。これも、ここを直すと自然と修正された。
これでREが取れ、再帰の変数を一個減らすことができ、メモ化再帰を用いてcodonでAC。
しかし、PyPyではACできず、なぜ？ と思ったが、メモ化再帰で使っているdictのせいで遅くなっていた。
再帰の回数は少なく、あえてメモ化する必要はない。各段階での文字の個数は前計算できるので、それを使えばPyPyでもACできた。
0 件のコメント:
コメントを投稿