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


可复制的 PDF 提取文本
The 24th Japanese Olympiad in Informatics (JOI 2024/2025)
JOI Open Contest
June 15, 2025
bubble
バブルソート機(解説)
小課題1 : ボタン1 を押す回数が10 回以下
ボタン1 に対するシミュレーションを定義通りに行うことができます(1 回あたりO(N) 時間).そのた
びに累積和テーブルを作成しておくことで,ボタン2 に対する答をクエリごとにO(1) 時間で計算できます.
小課題2 : L j = R j = 1
以下の解説において,インデックスの範囲に関する場合分けを減らすためにAN+1 = AN+2 = · · · = ∞とし
ます.
ボタン1 を押した回数をk とすると,答はmin(A1, . . . , A1+k) になります.このことを証明します.
Ai = min(A1, . . . , A1+k) とします.複数のi があるならばそのうち最小のi をとります.このAi は列の左
端(つまりa1)に到達するまで左に移動し続けて,ボタン1 がi −1 回押された時点で左端に到達します.
このあとa2 とスワップされてしまうこともありません.なぜならば,A2+k, A3+k, . . . がk 回目にボタンを押
す時点までにa2 に到達することは不可能だからです.
クエリに答えるには累積min のテーブルを前計算しておけばよく,O(N + Q) 時間で解くことができます.
小課題3 : 1 ≦Ai ≦2
ボタン1 を押したときの1 の移動の様子を考えると,
• ボタンを押した時点でその左側に少なくともひとつ2 があれば,左方向にひとつ移動する.
• そうでなければ移動しない.
ということが分かります.このことから,それぞれの1 が,k 回ボタンを押した後にどの位置に来ている
かは簡単に計算できます.二分探索により,最終的にl 番目からr 番目の間に来る1 の個数をクエリごとに
O(log N) 時間で計算できます.
さらに考察を進めて後述の小課題5, 6 と同様の性質を見つければ,クエリごとにO(1) 時間で計算するこ
ともできます.
バブルソート機(解説)– 1 / 2
The 24th Japanese Olympiad in Informatics (JOI 2024/2025)
JOI Open Contest
June 15, 2025
bubble
小課題4 : L j = R j
答を二分探索することを考えます.そのためには「答はx 以上であるか否か」の判定ができればよいで
す.x 未満であるものを1,x 以上であるものを2 に置き換えることで,小課題3 の状況でai を求める問題
が解ければよいです.
ある1 がai に移動してきているのは,
• k 回連続で左に移動した場合.
• k 回未満移動したあとそこに留まっている場合.
がありますが,それぞれ,Ai+k = 1 であるか,A1, . . . , Ai+k の中に1 がi 個以上あるかなどを調べれば判定
できます.
i + k について昇順にクエリを処理すれば,クエリあたりO(log N) 時間で解けます.
小課題5, 6
L j 番目からRj 番目までの和を求めるには,「先頭からnj 番目までの和を求める」というタイプの計算を
2 回行えばよいです.そこで,先頭nj 要素がどうなっているかを考えます.
次を証明することができます:任意のn, k に対して次の2 つは多重集合として一致する.
• ボタン1 をk 回押したあとのa1, . . . , an.
• A1, . . . , An+k を昇順ソートしたときの先頭n 個.
任意にx をとり,両多重集合についてx 未満の数の個数が一致することを示せばよいです.すると
Ai ∈{1, 2} のときに示せばよいことになります.これは小課題3 での観察から小課題2 と同様に証明でき
ます.
結局次の問題が解ければよいことになります:A1, . . . , An+k を昇順ソートしたときの先頭n 個の総和を求
めよ.
このクエリ処理には様々な方法がありますが,例えばクエリをn + k について昇順に処理すれば,セグ
メント木やFenwick 木でクエリあたりO(log N) 時間で答を求められます.解法によっては時間計算量が
O(log2 N) となってしまうこともありますが,定数倍が良いものであれば小課題5 あるいは満点が得られ
ます.
バブルソート機(解説)– 2 / 2