ABC 270 E — Apple Baskets on Circle

考察

かごを一周すると、空でない各かごからりんごを一つずつ食べる。この一周分の変化をまとめて計算できれば、大量の周回を飛ばし、最後の一周の途中だけを順番に処理すればよい。

一つずつ食べる方法では、食べる個数だけでも最大 101210^{12} 回の処理が必要になり、空のかごを通る移動もある。そこで、食べた個数から直接状態を求める代わりに、「何周したか」を決めたときの状態を調べる。

かごの番号を i=1,…,Ni=1,\ldots,N、最初の個数を AiA_i、食べる目標個数を KK とする。一周は、かご1から順に全かごを訪ねて、再びかご1の前に戻るまでの NN 回の行動を指す。非負整数 mm に対し、mm 周すると各かごをちょうど mm 回訪ねるので、かご ii から食べる個数は min⁡(Ai,m)\min(A_i,m)、残る個数は max⁡(Ai−m,0)\max(A_i-m,0) である。食べた総数を

F(m)=∑i=1Nmin⁡(Ai,m)F(m)=\sum_{i=1}^{N}\min(A_i,m)

と置く。各項は mm を増やしても減らないため、F(m)≤KF(m)\leq K の真偽は成功から失敗へ一方向にだけ変わる。

ただし、二分探索の前に全消費を分ける必要がある。最初の総数を S=∑i=1NAiS=\sum_{i=1}^{N}A_i とすると、制約は S≥KS\geq K で等号も許される。S=KS=K なら答えは全て0なので、そのまま出力して終了する。この場合、全て食べ終えた後は何周しても F(m)=KF(m)=K のままであり、「成功する最大の mm」は存在しない。例えば N=1,A=(1),K=1N=1,A=(1),K=1 でもこの問題が起きる。

以降は S>KS>K とする。Amax⁡=max⁡iAiA_{\max}=\max_i A_i と置けば、F(0)=0≤KF(0)=0\leq K が成功、F(Amax⁡+1)=S>KF(A_{\max}+1)=S>K が失敗となる。したがって有限の区間で最後の成功を探せる。

  1. lo = 0、hi = Amax + 1 とし、lo を成功側、hi を失敗側に保つ。
  2. hi - lo > 1 の間、mid = lo + (hi - lo) // 2 を取り、F(mid)≤KF(\mathrm{mid})\leq K なら lo = mid、そうでなければ hi = mid とする。
  3. 終了時の m=lom=\mathrm{lo} が最大の成功値である。各かごの残数を Bi=max⁡(Ai−m,0)B_i=\max(A_i-m,0) とし、あと食べる個数を r=K−F(m)r=K-F(m) とする。
  4. r=0r=0 なら BB をそのまま出力する。そうでなければかご1から番号順に走査し、Bi>0B_i>0 のときだけ BiB_i と rr を1ずつ減らす。r=0r=0 になった時点で止め、残った BB を出力する。

最後の走査が一巡で足りる理由は、次の一周の消費量にある。mm 周後に正のかごが CC 個あれば、次の一周ではちょうど CC 個を食べる。最大の成功を選んだので F(m+1)>KF(m+1)>K であり、残り rr は CC 未満になる。詳しい式は正当性で確認する。

例えば A=(0,2,4),K=3A=(0,2,4),K=3 では、F(1)=2≤3<F(2)=4F(1)=2\leq3<F(2)=4 より m=1m=1。一周後の B=(0,1,3)B=(0,1,3) から、残り1個を食べる。かご1は空なので飛ばし、かご2を一つ減らして B=(0,0,3)B=(0,0,3) を得る。同じ配列で K=2K=2 なら m=1,r=0m=1,r=0 であり、追加で減らさず B=(0,1,3)B=(0,1,3) が答えになる。

典型の発動条件

答え上の二分探索

同じ操作を一定回数まとめた効果を計算でき、その回数に対して消費量が単調なら、予算内で実行できる最大回数を探せる。ただし単調性だけでなく、成功・失敗の両端点が存在することも確かめる。総消費量が予算と等しい場合のように、いつまでも成功するなら先に処理を分ける。

bulk処理と端数simulation

周期的な操作では、完全な周期をまとめて適用し、残りだけを元の順序で処理する。端数が本当に一周期未満かは、もう一周期進めたときの消費量と比較して示す。

問題固有の要素

空のかごも含めて必ず右隣へ移動するため、一周で全かごを一度ずつ訪ねる。この規則から、空になった時刻を個別に追わずに min⁡(Ai,m)\min(A_i,m) で消費数を表せる。また、完全な周回の後は必ずかご1の前に戻るので、端数は番号順に処理すればよい。

正当性

S=KS=K の場合、ちょうど KK 個を食べた時点では全てのりんごを食べているので、全て0を返す処理は正しい。

S>KS>K の場合を考える。各かごを一周に一度訪ね、空でない間だけ一つ食べるため、mm 周後の消費総数は F(m)F(m)、残数は Bi=max⁡(Ai−m,0)B_i=\max(A_i-m,0) である。二分探索は成功・失敗の端点を保って区間幅を狭めるので、終了時には F(m)≤K<F(m+1)F(m)\leq K<F(m+1) が成り立つ。

Bi>0B_i>0、すなわち Ai>mA_i>m を満たすかごの個数を CC とする。各項の増分は Ai>mA_i>m なら1、それ以外なら0なので、

F(m+1)−F(m)=C,0≤r=K−F(m)<CF(m+1)-F(m)=C,\qquad 0\leq r=K-F(m)<C

となる。したがって、正のかごを先頭から訪ねて一つずつ食べれば、一周し終わる前に残り rr 個を食べ終える。これは元の操作と同じ順序なので、得られる残数も一致する。r=0r=0 の場合、mm 周を終えるより前に目標へ達していても、その後の周回末尾では何も食べていないため、残数は変わらない。よって追加操作をせず BB を返せばよい。

実装上の注意

  • 総数 SS、判定値 F(m)F(m)、各かごの個数には64 bit符号付き整数を使う。総和は最大 101710^{17} で、その範囲に収まる。hi や mid も同じ型で扱う。
  • S=KS=K の分岐を二分探索より前に置く。成功側の更新は F(mid)≤KF(\mathrm{mid})\leq K とし、等号を含める。
  • F(m)F(m) は元の配列 AA から求める。判定中に配列を減らさず、探索後に一度だけ BB を作る。あと食べる個数 rr と、かごに残る個数 BiB_i を混同しない。
  • 最後の走査では、減らす前に r>0r>0 を確認し、空のかごでは rr を減らさない。最初から r=0r=0 なら何も減らさない。

復習の核

  • 円環を大量に巡る処理では、まず一周後・数周後の各要素を式にできるか考える。
  • 二分探索の単調性を示したら、成功側と失敗側も実際に確認する。消費量が上限で飽和すると、最後の成功が存在しない場合がある。
  • 一括処理後の端数は「次の一周期で増える量」より小さいと示せば、一巡だけで復元できる。

計算量と制約

時間

O(Nlog⁡(Amax⁡+1))O(N\log(A_{\max}+1))。総数と最大値の計算に O(N)O(N)、区間幅 Amax⁡+1A_{\max}+1 の二分探索で一回の判定に O(N)O(N) かかる。残数の計算・最後の走査・出力も合わせて O(N)O(N)。全消費の場合は探索せず O(N)O(N) で終了する。

空間

入力配列と残数を保持して O(N)O(N)。入力配列を探索後に書き換えて残数を保持する場合も同じ評価となる。

制約との対応

1≤N≤1051\leq N\leq10^5、0≤Ai≤10120\leq A_i\leq10^{12}、1≤K≤10121\leq K\leq10^{12}、S≥KS\geq K である。空のかごを許し、全消費は先に処理する。残る S>KS>K の場合は Amax⁡≥1A_{\max}\geq1 で、探索の判定回数は最大40回となる。総和の最大値 101710^{17} は64 bit符号付き整数の範囲内であり、各判定・残数復元とも整数演算だけで行える。

出典

分類・前提・執筆情報

掲載状態: 収録済み

Apple Baskets on Circle の公式問題ページ(外部リンク)

最終確認:

学習上の位置付け

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

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

      主タグ: 単調境界探索

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

      学習の位置

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

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

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

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

      学習記録

      状況更新: 更新記録なし

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

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

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

      同じ単元の問題