← 返回题目列表

AtCoder · joiopen2025_b

B. 彩票

中文机器翻译题面 查看原题

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

くじ引き (Lottery) - 原题 PDF 第 1 页
原题PDF第1页
くじ引き (Lottery) - 原题 PDF 第 2 页
原题PDF第2页
可复制的 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