Codeforces Round 873 (Div. 1)

　B1まで二完。良い成績じゃないけれど、どうにかB1を通せたのは良かった。

コンテストへのリンク

コンテスト後のツイート

Codeforces Round 873 (Div. 1) pretestはB1まで。出来は良くないけどB1を通せたのは良かった。
A まずソート。A[i]が何番目まで使えるか考える。
B1 iを固定して、A[i:x]を差分計算して計算していく。これはstackと二分探索を使うとできる。PyPyだとTLEしたためRustに直してどうにかAC。

— titia (@titia_til) May 14, 2023

B2. Range Sorting (Hard Version)

　解説AC。

　全然分からなかったけど、こたつがめさんの実況放送の振り返り部分を繰り返し聞いたら理解できた。

・（B1をやっているときに？）ブロックに分ければ良いと気付く

・ブロックの個数を数える方針にし、ブロックの左端がiになるような(l, r)を数え上げる方針を立てる。

・j<i<kで、A[j]>A[k]となるような区間が含まれるとダメ。

・iから左方向への累積maxと(i, k)の区間minがあれば数えられる。

　いや難しい。方針を理解するのも難しいし、おおまかな方針が立った後、実装方針を立てるのも簡単じゃない。（コード自体は結構短く書けるのだが）

　B1を通したときは、[l, r]が何個に分けられるか数えよう、という方針から、lを固定したとき差分計算でどうにかしよう、と思って解いたので、ちょっとこの解法からは遠かった。

　ある区間が何回数えられるか？（主客転倒）みたいな方針も最初は考えたのだけど、上手くいかない気がしてしまったからねぇ。

　解説を見てからも（少なく見積もって）数時間かかった問題が、コンテスト時間内に解けるようになるのか、というのは結構疑問なんだよねぇ……。

　ただ、「ブロックに分けられるときの数え上げ」に帰着できるような問題をまた見る可能性はあるだろうから、そのときこの問題を思い出せるようになっていれば良いかな。