以下页面来自日本信息收集官方发布的原题PDF,已完整保存并渲染到本地。


可复制的 PDF 提取文本
The 24th Japanese Olympiad in Informatics (JOI 2024/2025)
JOI Open Contest
June 15, 2025
lottery
くじ引き(解説)
小課題1,小課題2 : Q ≦100, R j −L −j + 1 ≦100
簡単のため,L j = 0, Rj = n −1 として説明します.また,賞品が得られる玉の取り出しだけを考えます.
「賞品の総数K 以上を達成できるか」を判定する問題を考えます.まず,任意のi についてXi + Yi ≧K で
あることが必要です.
その条件下のもと,問題は次のように言い換えられます.
• 0 ≦ai ≦bi ≦K を満たす整数ai, bi が与えられる.
• 整数列x = (x0, . . . , xn−1) があり,はじめxi = 0 で初期化されている.「n/2 箇所に+1 する」という
操作をK 回繰り返してai ≦xi ≦bi が成り立つようにできるか否かを判定せよ.
この問題の必要十分条件は,∑ai ≦nK/2 ≦∑bi です.実際この条件が必要なことは明らかです.十分性
の証明について説明します.この条件が成り立つとき列x をai ≦xi ≦bi かつ∑xi = nK/2 となるように定
められます.このx が実現可能であることを示します.
x から「n/2 箇所に−1 する」という操作をK 回繰り返して(0, 0, . . . , 0) にできることを示せばよいです.
「xi が大きな方からn/2 箇所に−1 する」ことを繰り返す貪欲法により達成できることが帰納法により証明
できます.
以上で判定問題がO(n) 時間で解けるため,二分探索を利用して答をO(n log{maxi(Xi + Yi)}) 時間で求めら
れます.全クエリを通した計算量はO(Q max j(Rj −L j + 1) log maxi(Xi + Yi)) 時間です.
小課題1 ではXi, Yi の制約が小さいため,判定問題の一部を貪欲法のシミュレーションなどに置き換えた
解法も可能となるでしょう.
小課題3 : L j ≦Lj+1, R j ≦R j+1
小課題1 で解説した条件を,Xi, Yi を使って言い換えると次のようになります.
• Xi + Yi ≧K.
∑
• i min(Xi, K) ≧nK/2.
∑
• i min(Yi, K) ≧nK/2.
なおそれぞれの意味は,「袋i の玉が不足しない」「赤玉が不足しない」「青玉が不足しない」ということを
意味しており,その必要性は明白です.
くじ引き(解説)– 1 / 2
The 24th Japanese Olympiad in Informatics (JOI 2024/2025)
JOI Open Contest
June 15, 2025
lottery
これらが同時に成り立つK の最大値を求めることが課題ですが,3 つの条件それぞれについてK の最大
値を求めればよいです.最初の条件は単なる区間最小値クエリです.残り2 つの条件は同じ形をしている
ため,Xi に関する問題が解ければよいことになります.
小課題3 では,多重集合{XL j, . . . , XR j} が変化する回数はすべてのクエリをあわせてもO(N) 回しかあり
ません.よって,
• 多重集合への要素の追加・削除.
• K 未満の値の個数や総和の計算.
が出来るようなデータ構造を用いれば解くことができます.追加される可能性のある値が予め与えられて
いるので,座標圧縮してFenwick Tree などのデータ構造を用いれば解くことができます.
例えばO(Q log N log max(Xi + Yi)) の計算量で解くことができます.
小課題4, 5, 6
小課題3 で説明した解法を,さらに任意の区間クエリ[Lj, Rj) に対応させましょう.
Wavelet Matrix を用いることで解くことができます(他にも,永続セグメント木でほぼ同様の解法が可能
です).
Wavelet Matrix は,列X の要素全体でBinary Trie を作ったときに,「XL j, . . . , XRj のうちであるノードに
含まれるもの全体」が取得可能なデータ構造です.特に累積和テーブルと組み合わせることで,それらの総
和を求めることができます.
「XL j, . . . , XR j のうちでK 未満であるものの個数・総和」は区間[0, K) の分割に対応するノード群での総
和を計算することで,O(log max Xi) 時間,あるいは座標圧縮によりO(log N) 時間で取得できます.
これで本問題をO(Q log2 N) 時間で解くことができますが,満点を得るのはやや難しいと思います.求値
と二分探索を独立に行うのではなく,求値・判定を同時に行いながらWavelet Matrix を再帰的にたどるよう
に処理すれば,時間計算量をO(Q log N) にすることができて,余裕を持って満点をとることができます.
くじ引き(解説)– 2 / 2