第10回日本情報オリンピック 予選4

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

問題
   1年生 (A First Grader)

解説

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

解法1

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

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

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

解法2

解法1は無駄が多い(※)ので,次のようにするとよい.

と置けば

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

(※)について

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

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

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