ABC 424 E — Cut in Half

考察

最長の棒を一本ずつ割ると、操作回数が最大で十億回になる。そこで「ある長さを超える棒をすべて割り終えるまで」をまとめて数え、その直後の袋の中身を復元する。同じ長さの棒は個数だけを持てば、最後の順位も一本ずつ並べずに求められる。

長さの上限を決めると、必要な分割が決まる

長さの上限を D>0D>0 とする。元の棒 ii からできる長さは Ai/2qA_i/2^q に限られる。そこで、Ai/2q≤DA_i/2^q\leq D を満たす最小の非負整数を qi(D)q_i(D) と定める。

深さ qi(D)q_i(D) 未満の棒はすべて DD より長いので、必ず割る必要がある。分割を二分木とみると、深さ qi(D)q_i(D) までの完全二分木になり、葉は 2qi(D)2^{q_i(D)} 本、割った棒に当たる内部頂点は 2qi(D)−12^{q_i(D)}-1 個である。例えば長さ 88 を 33 以下にするには、8→4,4→2,2,2,28\to4,4\to2,2,2,2 と計三回割る。

各元棒は独立に数えられるため、すべての棒の長さを DD 以下にする最小操作回数は

need⁡(D)=∑i=1N(2qi(D)−1)\operatorname{need}(D)=\sum_{i=1}^{N}\left(2^{q_i(D)}-1\right)

となる。DD を大きくすると必要な深さは増えないので、この値は単調非増加である。need⁡(D)≤K\operatorname{need}(D)\leq K を満たす最小の上限を D∗D^* とし、これを探索する。

ここで、問題の「最長を割る」という順番も役立つ。DD より長い棒が残っている間、最長の棒も必ず DD より長い。従って実際の操作も、ちょうど need⁡(D)\operatorname{need}(D) 回でこれらの内部頂点をすべて割り終える。その時点では、各元棒から長さ Ai/2qi(D)A_i/2^{q_i(D)} が 2qi(D)2^{q_i(D)} 本ずつできている。判定に使った式から、途中の袋の中身まで分かる。

長さを整数に拡大し、境界を厳密に選ぶ

境界の近くを実数で探すだけでは、どちら側から深さを決めるかが曖昧になる。ここでは深さの上限から共通の分母を決め、整数の二分探索にする。

成功する判定では、各元棒だけで使う回数も KK 以下でなければならない。よって

2qi−1≤K,qi≤L=⌊log⁡2(K+1)⌋≤292^{q_i}-1\leq K,\qquad q_i\leq L=\lfloor\log_2(K+1)\rfloor\leq29

である。LL は整数 K+1K+1 の最上位の立っているビットの位置から求める。さらに一回割った長さも整数で表せるよう、倍率を S=2L+1S=2^{L+1} とし、元の長さを Bi=AiSB_i=A_iS へ拡大する。成功側で現れる長さ Bi/2qiB_i/2^{q_i} はすべて整数である。

必要回数が変わるのは、上限がいずれかの Ai/2qA_i/2^q をまたぐときだけである。最小成功境界では q≤Lq\leq L なので、D∗D^* もこの整数格子上にある。したがって拡大後の上限 d=SDd=SD について、最小の成功する整数を探せば、近似なしに d∗=SD∗d^*=SD^* が得られる。

失敗側を lo = 0、成功側を hi=max⁡iBi\mathtt{hi}=\max_i B_i と置く。長さが正の棒を有限回割っても最大長は正なので、ゼロは失敗側の番兵として扱い、判定器へ渡さない。hi - lo > 1 の間、mid = lo + (hi - lo) / 2 を整数除算で求める。need⁡(mid/S)≤K\operatorname{need}(\mathtt{mid}/S)\leq K なら hi = mid、それ以外なら lo = mid とする。終了時に採用するのは成功側の hi である。

判定では各 ii について、Bi≤d 2qiB_i\leq d\,2^{q_i} となる最小の深さを求める。深さが LL を超える場合、または必要回数の累計が KK を超えた時点で失敗とする。全棒の必要回数を巨大な整数まで足す必要はない。

境界に残った最長の棒だけを、一度まとめて割る

探索後、d=d∗d=d^* で深さを計算し直す。長さから本数への個数表 CC を空で初期化し、元棒 ii ごとに、拡大後の長さ Bi/2qiB_i/2^{q_i} の本数へ 2qi2^{q_i} を加える。使用済み回数を used=need⁡(D∗)\mathrm{used}=\operatorname{need}(D^*)、残り回数を r=K−usedr=K-\mathrm{used} とする。

この表の最大長は d∗d^* である。もしそれより小さければ、さらに小さい上限でも成功し、境界の最小性に反する。その本数を c=C[d∗]c=C[d^*] とすると、

0≤r<c0\leq r<c

が成り立つ。左側は成功側の判定から分かる。右側について、もし r≥cr\geq c なら、長さ d∗d^* の棒を全部割っても操作回数は KK 以下であり、最大長を d∗d^* 未満にできてしまう。

従って残りの操作は、この cc 本のうち rr 本だけを割って終わる。割ってできる棒は d∗/2d^*/2 であり、未分割の d∗d^* が残る間は選ばれない。個数表は一度だけ、

C[d∗]←c−r,C[d∗/2]←C[d∗/2]+2rC[d^*]\leftarrow c-r,\qquad C[d^*/2]\leftarrow C[d^*/2]+2r

と更新すればよい。r=0r=0 なら更新を省く。同じ長さが既にあれば本数を加算する。各元棒が一種類ずつ作る高々 NN 種類に、新しい長さは d∗/2d^*/2 だけなので、更新後も種類数は高々 N+1N+1 である。これが個別公式解説の種類数の上限に対応する。

例えば N=1,A=(1),K=2N=1,A=(1),K=2 なら、D∗=1/2D^*=1/2、q1=1q_1=1、used=1\mathrm{used}=1 である。長さ 1/21/2 の二本から一本だけを割り、最終的に (1/2,1/4,1/4)(1/2,1/4,1/4) を得る。D∗D^* より少し小さい失敗側を採用すると q1=2q_1=2、必要回数は三回になり、操作を使いすぎる。成功側の正確な境界を使う意味はここにある。

個数を使って順位を取り出す

個数表の長さを降順に並べる。現在見る長さを vv とし、X>C[v]X>C[v] なら、その本数を XX から引いて次へ進む。初めて X≤C[v]X\leq C[v] となった長さが答えであり、最後に倍率を戻して v/Sv/S を出力する。等しい長さは別々の棒として本数に含めるので、同率の順位もそのまま扱える。

典型の発動条件

答えの二分探索

上限を決めると必要な操作回数を数えられ、上限を緩めるほど必要回数が増えないときに使える。本問では最大長の最小値を探すことで、順位を求めるための袋の中身も復元できる。境界を求めた後の復元には、成功側・失敗側のどちらの状態が必要かまで確認する。

完全二分木の層数式とfrequency集約

同じ対象を繰り返し二等分し、同じ深さの対象が対称に振る舞うとき、全頂点を生成せず深さと本数で数えられる。深さ qq までなら葉数は 2q2^q、内部頂点数は 2q−12^q-1 である。さらに、同じ長さへの操作結果も等しいため、長さごとの本数で状態を集約できる。

問題固有の要素

最長から割るため、ある上限を超える棒を処理し終えるまで、それ以下の棒には触れない。この性質が、元棒ごとの独立な必要回数と実際の操作順を結び付ける。

また、最小成功境界に残る最長の棒をすべて割るだけの回数は残っていない。単なる単調判定だけでは得られないこの事実により、残余処理は一つの長さへの更新で終わる。反復処理をまとめるときは、境界の最小性から「次の段階へは進めない」と言えないかを考えたい。

正当性

上限 DD に対し、元棒 ii の深さ qi(D)q_i(D) 未満にある棒はすべて DD より長く、必ず割る必要がある。これらをすべて割ればすべての棒の長さが DD 以下になるので、必要回数はちょうど need⁡(D)=∑i(2qi(D)−1)\operatorname{need}(D)=\sum_i(2^{q_i(D)}-1) である。最長を選ぶ操作も、DD 以下の棒を割る前にこれらをすべて処理するため、この時点の長さと本数は個数表の初期状態に一致する。

必要回数は上限について単調非増加である。成功する深さは LL 以下なので、最小成功境界 D∗D^* は倍率 S=2L+1S=2^{L+1} の整数格子に含まれる。整数二分探索は失敗側と成功側を保ち、隣接した時点の成功側から正確な D∗D^* と各深さを得る。

境界での最大長が D∗D^* より小さい場合、または残り回数 rr が最大長の本数 cc 以上の場合は、KK 回以内でさらに小さい上限を実現でき、D∗D^* の最小性に反する。従って 0≤r<c0\leq r<c であり、以後の操作はすべて長さ D∗D^* の棒を一本ずつ割る。同率のどの棒を選んでも長さの多重集合は等しいため、一括更新後の個数表は実際の KK 回の操作後と一致する。降順に本数を引いて得る順位も一致し、その長さを倍率で戻した値が答えである。

実装上の注意

整数幅と回数の打切り

長さの拡大、二分探索、深さの判定、個数表のキーは64 bit整数で扱う。Bi≤109⋅230<260B_i\leq10^9\cdot2^{30}<2^{60} なので、整数の lo + (hi - lo) / 2 で中点を計算できる。探索は高々60回で終了する。BiB_i は最初に一度だけ計算する。

2qi2^{q_i} の計算も 1ULL << q_i などの64 bit演算にする。必要回数は累計が KK を超えたら失敗を返す。深さの上限を先に検査すれば巨大なシフトは不要であり、個数・使用回数・順位も整数のまま扱える。

倍率に一段分の余裕を持たせたので、復元時の最長の半分 d∗/2d^*/2 も整数になる。長さごとの本数は順序付き連想配列なら挿入時に集約でき、最後は逆順に走査すればよい。

深さはビット長を揃えてから一度比較する

深さを毎回ゼロから増やすと、一つの判定が O(Nlog⁡(K+1))O(N\log(K+1)) かかる。64 bit整数のビット長を使えば、一つの棒につき定数時間で求められる。

正整数 zz のビット長を b(z)=⌊log⁡2z⌋+1b(z)=\lfloor\log_2z\rfloor+1 とする。BiB_i に上限 dd のビット長を揃えるまで dd を二倍にした後は、もう一回二倍にするかどうかを比較すればよい。具体的には次の手順になる。

  1. q0=max⁡(0,b(Bi)−b(d))q_0=\max(0,b(B_i)-b(d)) とする。ビット長だけから、最小の深さは q0q_0 または q0+1q_0+1 に絞れる。q0>Lq_0>L なら直ちに失敗とする。
  2. Bi≤d 2q0B_i\leq d\,2^{q_0} を整数で比較し、成立すれば qi=q0q_i=q_0、しなければ qi=q0+1q_i=q_0+1 とする。ここでも qi>Lq_i>L を拒否する。
  3. 2qi−12^{q_i}-1 を必要回数の累計に加え、KK を超えたら失敗とする。

q0>0q_0>0 の場合、比較の右辺は 2b(Bi)2^{b(B_i)} 未満であり、2b(Bi)≤2Bi<2612^{b(B_i)}\leq2B_i<2^{61} なので64 bit整数に収まる。q0=0q_0=0 なら右辺は d<260d<2^{60} のままである。b(Bi)b(B_i) は前計算し、b(d)b(d) は各判定で一度計算する。C++20なら符号なし整数の std::bit_width を使える。ビット長の差が負ならゼロにする処理では、符号なし整数の減算による桁あふれを避ける。

浮動小数点への変換は出力時に行う

個別公式解説が述べる64 bit浮動小数点での正確性は、元の長さが整数で、二等分以外に長さを変えないことから理解できる。復元後の長さは Ai/2q (q≤L+1≤30)A_i/2^q\ (q\leq L+1\leq30) であり、二進表現の有効桁は高々30 bitなので、53 bitの有効桁を持つIEEE 754の double で厳密に表せる。ただし、整数に拡大した探索中点は最大60 bitであり、そのまま double に移すと厳密性は保証できない。

本手順では探索と集計を整数で完結させ、出力時だけ元の長さへ戻す。v=Ai2L+1−qv=A_i2^{L+1-q} の余分なビットは末尾のゼロなので、vv の double への変換と SS による除算も厳密に行える。出力は十分な桁数を指定する。

復習の核

  • 反復回数が大きいとき、「ある境界を超える対象を処理し終えるまで」の回数と状態をまとめて求める。
  • 二分探索後に状態を復元するなら、境界の値だけでなく、採用側と等号の扱いを確定させる。
  • 最小成功境界では、そこに残る最大値をすべて処理できない。この矛盾を使うと、残余操作の対象と回数を絞れる。
  • 値の種類と対象の個数を分けて数える。同率の対象をまとめても、順位のための本数は残す。

計算量と制約

時間

Amax⁡=max⁡iAiA_{\max}=\max_i A_i、M=Amax⁡2L+1M=A_{\max}2^{L+1} とする。上記のビット長による深さ計算と順序付き連想配列を使うと、全体で O(Nlog⁡M+Nlog⁡(N+1))O(N\log M+N\log(N+1)) 時間。長さとビット長の前計算が O(N)O(N)、高々 ⌈log⁡2M⌉≤60\lceil\log_2 M\rceil\leq60 回の判定が各 O(N)O(N)、境界での深さの再計算が O(N)O(N)、高々 N+1N+1 種類への本数の集計が O(Nlog⁡(N+1))O(N\log(N+1))、残余分割の更新が O(log⁡(N+1))O(\log(N+1))、降順の順位取得が O(N)O(N) である。64 bit整数の比較・シフト・ビット長取得を定数時間とする。深さを逐次増やす実装なら、探索部分は O(Nlog⁡(K+1)log⁡M)O(N\log(K+1)\log M) となる。

空間

O(N)O(N)。入力、拡大した長さとそのビット長、境界の深さ、および高々 N+1N+1 種類の個数表を保持する。N+KN+K 本の棒を生成する必要はない。

制約との対応

各ケースで 1≤N≤1051\leq N\leq10^5、1≤Ai≤1091\leq A_i\leq10^9、1≤K≤1091\leq K\leq10^9、1≤X≤N+K1\leq X\leq N+K、全ケースの NN の総和は 10510^5 以下である。深さ上限は29、倍率は高々 2302^{30} なので、探索する長さは64 bit整数に収まり、判定の総走査量は高々約 60∑N60\sum N となる。

同率の最大長が何本あっても r<cr<c なので未分割の最大長が残り、X=1X=1 の答えは D∗D^* になる。更新前は総本数が N+usedN+\mathrm{used}、更新で rr 本増えて N+KN+K 本になるので、X=N+KX=N+K も最後の長さへ正しく到達する。K=2m−1K=2^m-1 で一層を割り終えた場合は残り回数がゼロになり得る。KK や長さが二の冪の前後でも、整数のビット長と等号を含む比較により同じ手順を使える。K=109K=10^9 でも、残り回数に比例するループは発生しない。

出典

分類・前提・執筆情報

掲載状態: 収録済み

Cut in Half の公式問題ページ(外部リンク)

最終確認:

学習上の位置付け

主題の単元: 単調境界を証明して探索する

主題
追加で学ぶ技能
    なし
    既習技能

    主タグ: 単調境界探索

    補助タグ: 暗黙・対称な完全二分木の深さ算術

    執筆: abc-explanation-author1.1.1 / revision 3

    学習の位置

    体系上の位置: 単調境界を証明して探索する

    • 判定の単調性を証明し、二分探索の成功側・失敗側を設定できる。

    先に読む単元:

    この解説で扱わないこと:

    • 連続窓の両端を一方向に進める尺取り法、および真偽判定の単調境界を持たない三分探索・局所探索。

    学習記録

    状況更新: 更新記録なし

    復習設定更新: 更新記録なし

    端末内の保存状態を確認しています。

    要復習一覧 / 学習記録のバックアップ / 解説に戻る

    同じ単元の問題