天下一でひどいことになったので、その弔いに。
経過
開始前にEducationalってなんぞやと思って調べるも、過去問しか見当たらず。まあ教育的な問題が出るんでしょう、しらんけど。
A
過去問に似たようなのがあった。ウケる。単調減少な場所を見つけたらOK.
B
8の個数と場所を見ればできそう。1-indexedと勘違いして1WA. は？
C
問題名がうるさそう(こなみ)。ごじょほう。1715msってまあまあ危ないのでは？(3sなのでいけたけど)
D
まあまあ悩む。部分問題としてx=1で解くというのがあって、それがO(N)で解けた。それをいじったら元の問題も解けた。
前からsumを取ると、「a<=b<=c<=dなる添え字について-sum[a]+(-x+1)sum[b]+(x-1)sum[c]+sum[d]を最大化せよ」と言い換えられる。変数を固定して「1からi番目でのmax」を見ていけば、DPを4周回してできる。
DPが見えたので今日はいい日。
E
ラグランジュ補間って知ってますか？インタラクティブの提出方法は知らないですけどね (悲しい)。
なんでat most 50なのかは謎。一瞬なんか頭のいい方法があるのかとか思わせるためなのか？実際思ったし(ゴミ)。11回聞いて係数調べて全検で終了でした。なにそれ。
インタラクティブの使用でミスって手間取るも、なんとか通せた。手間取った分のゴミの提出はWAにカウントされないんですね、やさしい。
F
残り15分しかない状態で英語を読む気力がなかった。ゴミ捨てに行った。
結果と感想
・5完。penalty 228 (内1WA) でした。レートおそらく+187とバキ上げで、テンションがブチ上がった。
・Cまでに30分、Dまでに1時間かかっていて遅い。5完勢の中でも遅い。「はいはい」とか言って爆速で書けるようになったらいいんだろうなぁ。40分くらいでさばけるようになりたい。
・Eはインタラクティブ初ACなので時間は気にしない (45分)。ところでインタラクティブ問題のコードチェックの効率のいい方法ってあるのかな。今回は途中で切り取って投げるという原始的な方法で乗り切ったけど、今後もそれで行けるのだろうか。
・Open Hackいる？何も起きないようにお祈りしたら何も起きなくて、順位が15ほど上がった。
・Dは別に最初からsumを取らなくてもよかった。似た話題として「DはEars」説があり、昔解けなかったEarsをもっかい考えてみたが、なんとトケタ。たしかにこれはDと一緒だなぁ。これが教育的か...
・部分問題を考えるメソッドは効くなぁ。困難は分割せよ。
