「な、なんですのこれは……！」
お嬢様は大変困惑しておられました。日々忙しくお勤めを果たすメイドの私にとって、週末のこの時間はいつも楽しみでなりません。
今日もコンテストがあるから21:00以降は入るなと言われていたのですが、集中しているお嬢様は部屋の扉をちょっと開けて覗き見したくらいではこちらに気づくことはありません。
解けない問題を前に呻くお嬢様を見る至福の時間。このために毎日毎日過酷な労働をしていると言っても過言ではありません。
さて、うっすら見える画面からしてあれはたぶん……C問題ですかね？
おやおや珍しい。一応緑(ギリギリ)のお嬢様が300点問題に手こずるなんて……。
私は音を立てないようにノートPCを開いて確認します。
https://atcoder.jp/contests/abc189/tasks/abc189_c
あーなるほど。たぶんお嬢様が困っているのは……。
「おかしいですわ……普通C問題がこんなに難しいはずがない……」
解法はすぐ思いつきましたが制約はなんと$1≦N≦10^4$。わたくしの考えた解法は$O(N^2)$。つまり計算回数は最大$10^8$回……。
「pythonで間に合うわけがない……！」
精進中に何度「TLE」の文字に泣いたことか……！
今回はすでにB問題で1WA。(誤差をうっかりしましたわ。あれほど小数点に気をつけろと言われていたのに！)「とりあえず提出」でまたペナルティを食らうわけにはいかない……！
「一旦落ち着きましょう……」
机の角に積んだA4用紙(裏紙)を一枚取って図を書く。
……やはり区間の最小値を取って掛け算するくらいしか思いつきません。
「もしや……」
脳裏に浮かんだのは最近見た競プロ解説動画。
googleを開き、打ち込む。
『セグメントツリー』
これを使えば区間の最小値とかがすぐに出せる！(らしい。よくはわかってない)
「しかし」
結局すべての区間を調べるのだから$O(N^2)$は変わっていない気がする……。
それにもし想定解が「セグメントツリー」の300点問題が出てきたらchokudaiのツイッターを荒らさなければ……。AtCoder昔より厳しくなったといえどそんなはずはない……。いやでもこの前F問題が緑diffになっていましたわね……ならこれくらいの難化もありうる……？
いやいやそもそもセグメントツリーを使っても$O(N^2)$以上になるのは変わりないし……。
あ、もしかして遅延セグメントツリーとかそういう……いや遅延セグメントツリーがなにかは知らないけれど……。なんかセグメントツリーの上位互換みたいなやつ……。
あ、あれか？DPか？またDPか？なんだDPって？もうDPやめてくれ。
「ぐぅぅ……」
そろそろコンテストも終わりの時間……。Fはわかりませんでしたけどほかはそこまで難しくなかったですね。お嬢様の画面を見てしまっているので提出が出来ないのは歯がゆいところですが。
さて、お嬢様は……おや。
まだCが解けていないみたいですね。C問題を上下にスクロールしながら呻いているのが見えます。愉快。
お嬢様の順位は……お、Dは解けたみたいですね。解けないCを早めに保留したのは成長でしょうか。まあDも1wa出してますけど……。
コンテスト終了まで5,4,3,2,1……。
「お嬢様ー！」
「ぐぅぅ……」
「おじょうさまぁー！」
「な、入ってくるなと言ったのに！」
「いやいやもうコンテスト終わりましたから。どうでしたか出来は？」
「……まずまずね」
「あ、4完でしたか？」
「……さんかん」
「あ、ABCだけですか？」
「……ABとD」
「え？」
私はわざとらしく驚いて見せます。
「え？」
「……」
「C、解けなかったんですか？？？」
「……」
「あらー残念ですねー、じゃ、解答を見ましょうか！」
お嬢様からマウスをお借りし、C問題の解答を見せます。
読んでいくうちにみるみる顔色が変わるお嬢様。ああ、かわいい。
「え……これ……二重ループで通るの？」
「とおりますね。まあループの中の計算量が大したことないですしこれくらいなら」
「$10^8$回？」
「はい」
「いちおくかい？」
「はい」
「pythonでも？？？」
「pythonは無理じゃないですか？」
「……」
「……」
「……おのれchokudai……。pythonが通らない想定解だと……！！！」
お嬢様、大変お怒りですね。とってもかわいい。
「まあpypyなら通りますけどね。余裕で」
「……」
「ていうかなんでC++使わないんですか？強い人みんなC++おすすめしてますけど」
「……」
「まあpythonでも工夫すれば$O(N)$にできるんで通りますけどね。最大長方形問題ってご存じないですか？わりと昔の典型」
「……」
「ほらほらお嬢様、pypyで通してる人いっぱいいますよぉ？pythonでも解けた人ちらほらいらっしゃいますねぇ」
「……すいませんでした」
ふふふ。かーわいい。
「さ、一緒に解説放送見ましょ！」
「次はとおすぅ……」
ゲーミングお嬢様みたいなやつを書きたかった。
およそQiitaに投稿する内容じゃないけどこの話がわかる人間が他の場所を見る気がしなかったのでここに投げる。