ABCEの4完1RE
各問題
A - TLD
後ろから見て、最初に . が見つかった場所の後ろの文字列を出力します。
B - Langton's Takahashi
いわれたとおりにシミュレートします。
C - Perfect Bus
Aを順番に足していき、途中の合計値の最小値を最終的な合計値から引くと答えになります。
途中でマイナスになったところは非負になるように調整する必要があるし、途中が常に正数なら最も少ないところを0に調整する必要があるということです。
D - Synchronized Players
メモ化再帰では全然間に合わず。なんもわからず。
E - Smooth Subsequence
各数字ごとにそこまでで最長いくつの数列を作れるかで DP できそうですが、A も N も <= 500000 なので単純にはいきません。
A が取りうる値の範囲が 1 <= A <= 500000 なので、そこまでで最長いくつの数列を作れるかをセグメントツリーで管理して、A_i に対して A_i - D から A_i + D の範囲で最大のものに 1 を足したものと A_i との max を A_i に設定する、を繰り返していけばできます。
一か所 500001 を 5000001 としてしまう痛恨のミスで 1RE。
まとめ
D がさっぱりだったものの E が取れたのでなんとか緑パフォ上位で耐え（耐えてない）。
