AtCoder Regular Contest 079 E - Decrease (Judge ver.)

ポエム


制約大事ですよね。


突然なんじゃってなるけれど、nが50と言われると結構回すんだなってなる。


つまり、(これはいい癖なのか悪い癖なのかわからないけれど)始めについつい考えてしまう下手な貪欲をあきらめるいい材料なわけですね。


間違った方針をいつ切り捨てられるのか、ここら辺はほんと大事で、数日掛ければ問題が解けるけれどコンテスト中には解けないってことの大きな要因の一つだと思うのですよ。


今夏はサンプルケースも親切で、全部見渡すと「結局最後の方はシミュレーションするしかなさそうだけれど、めっちゃ大きい数来られたら当然無理なのである程度削りたいね。」って気持ちになります。


今回でいう「できるところまで削る」みたく、二段階でやっていく考えはなかなか出にくい(一通りの方針で通したくなる)けれど、この類の問題ではちゃんと頭に置いておきたいですね。



あとあと、「できるところまで削る」について、ちゃんと計算量は考えないとですね。O(n^3 log n)はn=50だと大丈夫です。



n-1回連続で同じところを削ることでできる可能性があるはずなので、n^2以上にはしないといけないはず(適当)。