公式

C - Fair Coin Partition 解説 by maspy

ヒント集 → https://atcoder.jp/contests/arc210/editorial/14522

本解説において，コインを分配するといえば，\(M\) 人に一人当たりに配る価値が等しくなるように配ることを表すこととします．

[1] 方針

価値が \(10^i\) のコインを，コイン \(i\) と呼ぶことにします．

答が \(10X+Y\) （\(0\leq Y\leq 9\)）であるとします．価値 \(10X+Y\) を持つコインの集合は，価値 \(1\) のコインを \(Y\) 枚以上含みます．よって価値 \(10X+Y\) を分配できるならば，価値 \(10X\) も分配できるので，まず，「価値 \(10X\) を分配できるような最大の \(X\)」を求めることを考えます．

この場合には，コイン \(0\) は必ず \(10\) 枚単位で配ることになるので，

  • コイン \(0\) をコイン \(1\) に可能な限り「両替」する．つまり，\(10\) 枚のコイン \(0\) を \(1\) 枚のコイン \(1\) に置き換えることを可能な限り繰り返す．
  • コイン \(1, 2, \ldots, N-1\) を \(M\) 人に，\(1\) 人あたりの価値が最大になるように分配する．

ということをすればよいです．

この上で \(Y\) を最大化することを考えます．この端数部分にはコイン \(1, 2, \ldots, N-1\) は使うことができません．よって，

  • コイン \(0\) をコイン \(1\) に可能な限り「両替」する．つまり，\(10\) 枚のコイン \(0\) を \(1\) 枚のコイン \(1\) に置き換えることを可能な限り繰り返す．
  • コイン \(1, 2, \ldots, N-1\) を \(M\) 人に，\(1\) 人あたりの価値が最大になるように分配する．ただし，「両替」によってできたコイン \(1\) がなるべく多く余るようにする．
  • 「両替」によってできたコイン \(1\) のうち余ったものを，コイン \(0\) に戻す．
  • コイン \(0\) を最大枚数ずつ分配する．

ということをすればよいです．

[2] 再帰関数による実装

以上を踏まえて，ここでは再帰関数を用いた実装方法を解説します（ほとんど同じことを，再帰関数を使わずに実現することも容易です）．

次のような再帰関数 \(f(i,k)\) を設定します．

  • \(f(i, k)\)：コイン \((i-1)\) からの両替によってコイン \(i\) を \(k\) 枚余分に得ている状態から始める．コイン \(i, i+1, \ldots, N-1\) を最大価値ずつ分配する．ただし，その中でも両替によって得たコインをなるべく余らせることとする．

\(f(i,k)\) は次のような再帰的な処理によって実現できます．

  • \(A_i+k=10a+b\) （\(0\leq b<10\)）とするとき，\(10a\) 枚のコイン \(i\) を \(a\) 枚のコイン \((i+1)\) に両替して，\(f(i+1,a)\) を実行する．
  • \(f(i+1,a)\) で余ったコイン \((i+1)\) を両替してコイン \(i\) に戻す．
  • コイン \(i\) をなるべく多くの枚数ずつ \(M\) 人に分配する．
  • この一連の処理において，コイン \((i-1)\) からの両替によって得たコインがなるべく多く余るようにする．コイン \(i\) が \(c\) 枚余るとき，コイン \((i-1)\) からの両替によって得たコインが \(\min(c,k)\) 枚であるようにできる．

あとは適当な終了条件を適切に実装すればよいです．以下の解答例も参考にしてください．

投稿日時:
最終更新: