第１０回日本情報オリンピック　予選４

2010年12月23日
情報オリンピック日本委員会

解説

数字の間にある「+」か「-」を入れる場所を「穴」と呼ぶことにする．また，書かれているn個の数字を左から順にa₀,…,a_n-1とする．

解法１

数字がn個並んでいるとき，穴がn-2箇所あるので，最も単純な方法としてn-2箇所の穴への「+」or「-」の入れ方を（再帰呼び出しなどで）全て試してみてそれぞれ正しい数式になっているかを判定するという方法が考えられる．

この方法だと2^n-2通りの数式を調べる必要があるのでn=100程度のデータを現実的な時間で解くことはできないが，いくつかのテストケースの答えを出すことができる．また，計算の途中で0以上20以下に収まらない数が現れる場合を除いていくと多少調べる量が減る．

実装は例えば下の擬似コードのようにすればよい．

long long answer = 0; //64bit整数
void calc(int position, int partialsum){ //左から(position-1)番目の穴まで「+」か「-」が入っていてそこまでの計算結果がpartialsum
  if(position == n-1){ //穴を全て（n-2個）埋めたら正しい数式になっているかチェックする
    if(partialsum == an-1) answer = answer + 1; //正しい数式なら答えのカウンタを1増やす
  }else{ 
    if(partialsum - ak ≧ 0) //「-」を入れて0以上なら次の穴に進む
      calc(position + 1, partialsum - ak); 
    if(partialsum + ak ≦ 20) //「+」を入れて20以下なら次の穴に進む
      calc(position + 1, partialsum + ak); 
  }
}
//calc(1,a0)で答えが求まる

解法２

解法1は無駄が多い（※）ので，次のようにするとよい．

f(k,B) := 『左からk個の穴に「+」or「-」を入れて「a₀からa_kまでの部分の和」をBにする方法の数』（0≦k≦n-2, 0≦B≦20）

と置けば

• f(k+1,B) = f(k,B-a_k+1) + f(k,B+a_k+1)　　　（0≦B≦20でないときf(k,B)=0と考える）
  
• f(0,a₀) = 1
  
• f(0,B) = 0　　　（B≠a₀）

よりkが小さいほうから順にfの値を求めていくことができる（求める答えはf(n-2,a_n-1)）．kの取る値がn-1(＜100)通りでBの取る値は21通りで各f(k,B)を求める操作は定数時間でできるので，この方法だと一瞬で答えを出すことができる．

（※）について

すなわち，穴への「+」or「-」の入れ方を全て試すアルゴリズムというのは，例えば，左からk個の穴に「+」or「-」を適当に入れて「a₀からa_kまでの部分の和（☆）」がAになったとき，

『残っている(n-k-2)個の穴に「+」or「-」を入れて「a_k+1からa_n-2までの部分の和」をa_n-1-Aにする方法の数（＊）』

を求めることになるのであるが，左からk個の穴をまた別の方法で埋めて（☆）がAになった時も（＊）を1から求めているのである．（＊）の値はいつ計算しても（=左のk個の穴への「+」or「-」の入れ方によらず）不変であることは明らかなので，これは無駄な計算である．

これを改善するには，1度（＊）を計算したらそのことを記憶しておいて次回以降は計算を省くようにすればよい．それには，kとAから「（＊）を既に計算したか」「（＊）の値（既に計算している時）」の情報を引き出せる2次元配列を持っておけばよい．これは実は解法２と本質的に同じになる．