← 返回题目列表

AtCoder · joiopen2025_a

A. 冒泡排序机

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

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

バブルソート機 (Bubble Sort Machine) - 原题 PDF 第 1 页
原题PDF第1页
バブルソート機 (Bubble Sort Machine) - 原题 PDF 第 2 页
原题PDF第2页
可复制的 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