2完。久しぶりのrated、楽しかったし、悔しい。昨日のABCはかなり調子が悪かったので、今日はティアキンをやらず、ABCの復習以外はあまり疲れることをしないようにすごした。夕方に昼寝ができたのはよかった。最近の調子の悪さを考えると、かなりいい状態で臨めた。
A - Reverse and Count
解ける問題ではありそうだが、かなりしんどい。途中でBを読んで、難しいBよりは簡単でしんどいAをやろうという気持ちにした。
Kから1を引いておき、自分以下のものがK個存在する最小のものを答える。順列は0-indexedにしておき、指定した数がどこにあるかテーブル引きできるようにしておく。現在考えている区間のサイズをMとする（最初はN*(N+1)/2）。普通に先頭から決めていく。先頭の数が小さくなるか変わらないかおおきくなるか。変わるのはN-1通りしかない。小さくなる個数は愚直にカウントする。Kと比較して、小さくなるなら右側の数を（コピーしてから）ソートしてK番目の数のAでの位置をテーブル引きしてそれと入れ替わるようにreverseして出力。大きるなるときも同様。そうでないとき、長さが1小さい問題に帰着できる。Kから小さくなる個数を引いて、Mから変わる個数を引く。長さ1の区間でreverseして順列が変化しない場合があるのが厄介そうだが、そういうのは真ん中に残るので、この処理で最後までreverseされずに残りそう。
B - Triple Pair
Cも読んで、Cはすぐに解けなさそうなので、すぐに解けるチャンスがありそうなBをやる。
入れ替えも区別するのが厄介そうだが、とりあえず区別しないやつで考えてみる。3つの中の最大値を固定する？いや最大値はN通りあるのでダメ。よく考えると、2個の正整数の組をカウントするのとそんなに変わらない問題だ。これは反比例のグラフみたいなのを想像して、対称なのでsqrt(N)まで見ればいい。最初よくわかってなくて、そういう組全体の個数を求めたりしてたけど、知りたいのは2数が等しいときの個数と、等しくないときの入れ替えを区別しない個数だ。斜めの線より上をカウントする感じ。元の問題に戻ると、この組が3個の数の大きい2つになるようなものをカウントすればいい。3数が等しいときは簡単。大きい2数が等しく残りが等しくないときは、等しいやつより小さい数の個数の3倍。で、5 3 3 みたいなやつは、さっき「斜めの線より上」で数えた。9 7 2 みたいのは、「斜めの線より上」に 7-1 を掛けながら足していってその6倍。
え、中央値固定するのやべえな。いやーそれは思いつかないなあ。いやあ。
C - Power Up
Dを読んでから順位表を見てCに専念する。
入力が個数であるかのように実装を始めてしまい、最終的にサンプルが全然通らないことに。この勘違いにより、個数の総和が（ほんとはNなのに）めっちゃ大きくなると思ってしまい考察の方向性もずれていった。最初に書いたのが再帰で、2*10^5+100までやると（スタックオーバーフローかなんかで？）出力されない現象があった。タテに累積和とってヨコに返すみたいなので頭が焼き切れる。解けそうだけど自分にはわからないという感覚（結局違ったっぽいけど）。けっこう経ってから、愚直を書いて高速化しようと思い立ち、書くけどサンプルが無限に合わない。最初に書いた勘違いのせいで正しく書いても合わないんだけど、それがなくてもめちゃくちゃ時間かかった。
悔しい。本体とまともに戦ってない。調子が悪かったわけでもない。あえて言えば勘が鈍っていたが、まあ単に力不足。悔しい。ARCだった。
（追記）手元で落ちる再帰、コードテストで動くので提出したらAC。とりあえずスタックサイズ10倍にしたら動くね。
