昨夜から熱があり、たぶん夜中がピークで、起きたときには治りかけという感じだった。しかしまだ熱はけっこう高かったので今日はずっと横になっていた。夕食後くらいでだいぶ楽になったので、ぷよぷよ最強リーグは観た。ABCもいつものパフォーマンスを出せたと思う。ABCDFの5完。Eも10分遅れで通した。しんどいセットだった。
A - Jogging
クソムズ。1秒単位で何メートル進んだか求めて足すのをX回回す。
B - Perfect String
Aよりは楽。相異なるという条件はソートして隣同士を比較すればいい。大文字小文字をそれぞれ1個でも含むというのはビットフラグでやった。「両方1個はある」の否定になったとき答えの変数を条件を満たさないほうへ変える（ややこしい）。
C - Just K
全探索やるだけ。しかしこれもけっこう難しいと思うんだよな。俺は青コーダーだからできるけど。
BもCも問題文の通りに実装するだけだけど、最近はこういう問題の複雑さというか階層の深さが上がっているイメージ。
D - Index Trio
A_jは1以上なので両辺にA_jを掛けても同値。入力はソートしてしまってもいいが、そもそも何が何個かをカウントしておくだけでいい。同じインデックスを複数回選んでもいいことに注意する。積を固定して考えて、約数全列挙。積が平方数のときだけ注意すれば大丈夫。
調和級数で解き直した。こっちのがだいぶ楽だね。固定するのは積じゃないのかあ。
E - RLE
個数の桁数が関係してくるのかなり嫌らしい。全然わからなかったが、しばらくしてDPを思いつく。3乗で解ける。これを2乗に落とすということだろうか。「またDPかよ」と思いFに行った。
斜めに累積和を持てば解けそうだ。しかしそこからが大変。解けそうだと思ってからも時間は30分あったが、形になったのは終了直前で、間に合わなかった。普通にDPテーブルを持ち、単に置くのではなく左下の要素との和を入れる。これで、1桁から4桁までのそれぞれについて斜めの区間和がO(1)で求まる。問題は累積和がはみ出すとき。はみ出したら外側は全部0なので引き算しないだけで済むけど、判定が面倒というか難しい。出発地点が外なら0-0だし、終端が外なら引かない。いや今言葉にするとそのまんまなんだが、本当に難しかったし、使う変数も多いのでミスも出た。文字の選び方が25通りだったり26通りだったりする問題は、最初の同じ文字の区間が必ず1個存在するので、全部25通りで求めてから26/25を掛ければいい。ここのやり方もけっこう迷走した。累積和だからその場で25倍しないといけないし、26倍かどうかの判定もそういえば難しいし。
F - Ignore Operations
t=1となるクエリがなければ小さいものK個を無視するだけ（と最初思ってたけど正の数は無視しちゃいけない）。最後のt=1クエリを固定して考えても同じ。これは後ろから考えれば各t=1クエリに対しそれを使うときの最大値が求まりそうだ。priority_queueを使うが、小さいものをK個まで保持するには最大のものを取り出す必要があるのでそのまま使えばいい（最初逆に書いてしまった）。ここからがかなり面倒。priority_queueは総和を管理して、K個を超えて入っていたら大きいものを取り出す。t=1が現れるたびにKをデクリメントする（そこまでのt=1を全部消す必要があるため）。実装上は、最初にt=1, y=0のクエリがあると考える。いや最初はこれが全然見通し立たなくて実装中もすごい負荷かかってたんだよ。
