Codeforces Round 932 (Div. 2)

　Dまで。

　このコンテストで久しぶりに紫から薄橙へ戻れた。紫に落ちていたときは非常に辛かった。戻れて良かった。

コンテストへのリンク

コンテスト後のツイート

Codeforces Round 932 (Div. 2) Dまで。
A sかs[::-1]+sか。
B 全体のMEXと同じMEXとなる配列二つに分割できるか？
C bでソート。DP[i][x]をiまででx個作れるときのコストのに似たやつとする。コストではなく、そこまでのAの合計-B[i]を入れると判定できる。
D 図を描くとそれぞれ線分なので足し引き。

— titia (@titia_til) March 5, 2024

E. Distance Learning Courses in MAC

　解法ツイートは見たけど、コンテスト中に考えていたことで合っていたのでほぼ自力AC。

　上位bitから見ていく。

　たとえば、あるクエリで、3つ目のbitについて考えているとき、[6,10]と、[9,11]のどちらから3つ目のbitを取るかというと、後者から取るべきである。そうすると、前者から7が取れるため、以下のbitは全て立てられることが分かる。

　こういう風に考えると、[6,10]から3つ目のbitが立っているものを選択するときは、他に3つ目のbitが立っている区間がないときである。そして、そのときは（3つ目のbitが立っている）[8,10]だけ考えれば良いことが分かる。

　なので、他に３つ目のbitが立っているときは処理を終わらせることにすれば、次、２つ目のbitを考えるときは、[6,10]を[8,10]に更新して考えて良い。

　そうやって更新していくと、ここでこの区間からこのbitを選択するのか？　ということを考えずに済む。

　というわけで、（こういう更新をした上で）

・ある区間にそのbitが立っているものが何個あるか？

・ある区間にそこで更新を終えてよいやつ（さっきの「7」みたいなものが含まれるやつ）があるか？

　が分かれば良い。

　これはセグ木を二つ使えばできる……と思って実装していたが、PyPyではTLEやMLEが取れなかった。

　落ち着いて考えると、両方累積和で処理できますね。セグ木なしで実装してAC。

　アイディアは間違っていなかったけど、コンテスト中はセグ木実装しか考えていなかったので、コンテスト中ACするのは困難でした。