titiaのノート: Codeforces Round 1120 (Div. 2)

2026年9月15日火曜日

　C1まで。

　Div. 1とDiv. 2が分かれている回でDiv. 2に出なくちゃいけないこと自体悔しいのに、そこで大失敗してしまった。

コンテスト後のツイート

C2 [l,r]から少なくとも一個は使う、という情報がいっぱい来る。包除原理かと思ったができず、コンテスト終盤にセグ木では？　と思ったが答えが合わず。
— titia (@titia_til) September 12, 2026

C2. Floor of MEX (Hard Version)

　結局、次の問題が解ければ良い。

　自然数1,2,...,nからいくつかを選ぶ場合の数のうち、

・[l_i,r_i]から少なくとも一つ選ぶ

　という条件Q個を満たすものの個数を求めて下さい。

　これをO(n+Q)くらいで解ければ良い（logが付いても良い）のだが、解けなかった。

　コンテスト中は包除原理を主に考えていた。

　これらの条件のうち、満たさない個数が偶数個の個数は求まるのだろうか？　などと。この方針は筋が悪かった。

　これはもっと直接的にDPで求めることができる。

・DP[i]を、「1...iについて条件を満たし、iを選んだときの求める個数」

　とすれば良い。

　こうすると、[l_i,r_i]から少なくとも一つ選ぶという条件は、「r_iより大きいjについて考えたとき、その一つ前に選んだ数はl_i以上である」という条件に直すことができ、それを利用すると累積和を使えばDPが回る。

（なお、DP[i]=「1...iについて条件を満たす場合の数」としても答えを求めることができるが、ちょっと遷移が複雑）

　これくらいの問題は簡単に解けなくちゃいけないんだろうけど……。筋の悪い解法にハマって抜け出せなくなってしまった。

　解説AC。

　「後ろから見る」という方針を知っても自力では答えに辿り着けず。

　降参位置を管理して解くのだが、そうできるポイントは、

　「ある降参位置で新しいチャンピオンが勝てた場合、そのチャンピオンのpowerは、以前のチャンピオンのpower以上になる。そのため、それより右にある降参位置を順に再評価できる。」（ChatGPTに整理してもらったもの）

　ということだった。

　これに気付ければあとはデータ構造を使ってがんばる問題になるが、その実装もなかなか大変だった。