3完早解き勝負とは思わんよね。結果的にはわりといい順位だった。
A - Thumbnail
設定が難しくてサムネの話なの忘れた。わかってみればABCのBだ。怖がらなくてもやるだけ。
B - Sum AND Subarrays
これも怖い見た目をしているが、よく見ると部分列の美しさを全列挙できる。400点だからね。階層が深くて問題を把握できないと思っていたが、ここまで来れば、あとは列挙したものからいい感じにK個選ぶだけだ。最大値を求めたいので、上位ビットから見ていく。K個以上の数で立ってるビットのうち最上位のものは採用するに決まってるので、それ以外は捨てる。それを繰り返せばO(N^2*log(max(a)*N))くらいで行ける。10^6にlogがかかるの珍しいけど、まあ実行時間制限がいつもより微妙に長いしね。vectorをswapすることで定数倍に最低限の配慮。12msで拍子抜け。今回は計算量が顔なじみのやつじゃなくて多少の負荷があった。
C - k-DMC
ただでさえわからんのにkが設定されてるとか。DとCではさむ、あるいはMから左右を見る。とりあえずkがNの場合を考える。この問題が解けたらk=Nのケースも解けてるはずだからそれがわからないんじゃ話にならない。DMCが入り交じった文字列で色々考えるが、複雑そう。計算量的には、クエリ毎にO(N)の時間をかけられる（そういう解法とはかぎらないけど）。Mの右にあるCの数は累積和でわかる。Dの右にあるMについてそれを足せばいいのかな。じゃあそれも累積和にしたら？これはいけそう。一般のkについては難しそうだが、あれ、この削られるCの数って Mの個数*区間の右にあるCの数 で簡単に求まるのでは？累積和をきれいに書いて、本体部分の実装もけっこう軽い。「解いてる感」がある。解いたあとでも難しかった感触がありつつ多くの人が解けている。かなり満足感の高い問題じゃないだろうか。
ところでDMCという文字たちはこの問題の本質に何も関係ないのにDMCで考えちゃうのよくあるね。
DとE
主にDの部分点を考えていた。回転は相当難しそうだが、同値類と考えるとD=1なら任意の配置にできるんじゃないかと気づく。正方形に配置して、一番大きいやつたちを上手く配置すれば。縦横別々に考えられるか。ループさせてもっとも離れた場所を見つけてそのぶん節約できる。しかし、正方形より縦横どちらかだけ細くできる場合があることに気づいた。どうしようもない。縦横どちらに使うかを全部に対して決めないといけない。そもそも部分点は何が楽なのだ？部分点なら、どれを基準にするか900通り試せるってことか？それでいけるかもわからんが。
Eは（かなり考えて）置換か。いい問題っぽさがあるので解きたいけどなあ。
