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について条件を満たす場合の数」としても答えを求めることができるが、ちょっと遷移が複雑）
これくらいの問題は簡単に解けなくちゃいけないんだろうけど……。筋の悪い解法にハマって抜け出せなくなってしまった。
0 件のコメント:
コメントを投稿