問題5 解説

 まず,誰でも思い付くのは素朴な全数検査法である.そのためにはすべての組合せをどのように生成するかが問題になるが,次のように考えるとよい.
 n 種類のものをそれぞれ a1 個, ..., an 個選ぶとすると,条件より m≦ai≦r (i = 1, ..., n) かつ a1 + ... + an = r である.したがって,m≦ai≦r を満たす整数の組 (a1, ..., an) をすべて試せばよい.しかし,この組合せの個数は (r - m + 1)n 通りもあるので,r - m や n が小さくないと時間内に計算が終わらないほど実行時間がかかるし,その値自身が32ビットを超える大きな数になると対処がむずかしくもなり,すべての入力データに対して正しい答を求めることはできない.

 次に,必要な箱の個数を n, m, r の式で表すことを考える.しかし,入力データの中には箱の個数が 32 ビットや 64 ビットでは表現できないものがあるので,計算が途中でオーバーフローしないような方法で計算しなければならない(この部分はプログラミング技能が求められるところである).IOI 本番の問題を解くためには,プログラミングの技能以上に数学(特に組合せ数学)のセンスが必要であるため,この問題はそのようなことを峻別する目的を持った問題として作った.
 式の求め方は後述するが,必要な箱の個数は (n + r - mn - 1) ! / {(n - 1) ! × (r - mn) !} である. n, m, r の値が大きいと単精度数(32 ビット数)では表現できなくなるので(例えば,入力データ in5 の n = 10000, m = 0, r = 10000 では箱の個数は 10 進数で 6018 桁にもなる),配列を使って多倍長計算をしなければならない.すなわち,配列 a とその配列要素 a[0], a[1], ・・・, a[k] を使って p 進数

  pkpk-1 ... p1p0    (各 i = 0, 1, ..., k に対して 0≦pi≦p - 1)

を配列要素の並び

  a[k], a[k-1], ..., a[1], a[0]    (a[i] は pi の位の数,すなわち pi を表す)

で表し,筆算で計算するように,整数の掛け算や整数による割り算を行う. このとき,注意しなければならないのは,配列の大きさをどのくらいにするか(すなわち,何桁取っておけばよいか)ということである.N ! の桁数は log10N !+1以下なので,n, m, r から前もって知ることができる.実行時間は,p = 10 としても,最も時間のかかる入力データ in5 でも10分以内で終了するように n, m, r を選んである.p を大きくするほど実行時間を短くすることができる.

 さて,上述の (n + r - mn - 1) ! / {(n - 1) ! × (r - mn) !} は n+r-1Cr に等しい.たとえこの値が 32 ビットで表現できるとしても,(n + r - mn - 1) ! / {(n - 1) ! × (r - mn) !} のまま計算しようとすると,(n + r - mn - 1) ! の値を計算するときにオーバーフローを起こすことがある.そのようなことを避けるためには,nCr の漸化式

  nCr = n-1Cr + n-1Cr-1

を使うことも有効になる(ただし,この問題の入力データセットに対しては有効ではない). 再帰的に計算することもできるが,n, r が小さい方から計算する方が有効なこともある(動的計画法と呼ばれる手法.この問題では有効ではない)が,それについてはここでは述べない.

 当初の作題においては次のような意図があった(最終的には,必ずしもそのようになっていない).
  1. 小さな入力データについては全数検査で計算できること.
  2. 大きな入力データでは全数検査が破綻すること.
  3. 数学的な考察により箱の個数を n, m, r の式で表すことができれば,入力データのうちの何個かは比較的容易に計算できること.
  4. さらに計算の工夫をしないと5個すべての入力データに対する答までは計算できないこと.

 最後に,箱の個数が (n + r - mn - 1) ! / {(n - 1) ! × (r - mn) !} であることの説明をしておく. 高校の数学でも学習するように,n 個の(異なる)ものの中から r 個を取り出す組合せの数は

  nCr = n ! / (n-r) ! r !

である.一方,異なる n 個のものから,同じものを何度でも選んでよいとして r 個選ぶ選び方を重複組合わせといい,その総数を nHr で表わすと,

  nHr = n+r-1Cr

である.なぜなら,n 種類のものをそれぞれ a1 個, ..., an 個選ぶとすると,上述したように,0≦ai≦r (i = 1, ..., n), a1 + ... + an = r であるから,選んだものを 0 で表すと,

  0...010...01 ... 10...0  (左から順に,a1個,a2個, …,an個の 0)

という 0, 1 の列と解 (a1, ..., an) が 1 対 1 に対応する(つまり,このような列の個数と解の個数が同じである).このような列の個数は 0 (r 個)と 1(n - 1 個)を合わせた r + n - 1 個を使った列の作り方(= n - 1 個の 1 をどのように配置するか)の個数に等しく,それは n + r - 1 個から n - 1 通り可能な 1 の位置から n - 1 個の位置を選ぶ選び方(順列)の個数に等しく,それは n+r-1Pn-1 = n+r-1Cr に等しい.

 さて,この問題は条件 0≦ai≦r を m≦ai≦r に変えたものであるが,bi = ai + m とおくと条件は 0≦bi≦r (i = 1, ..., n), b1 + ... + bn = r - mn と同値である.よって,n+r-mn-1Cr-mn が求める箱の個数である.