IT業界人、特にプログラマーにとっては恒例のイベントとなりつつある、GoogleのDevQuiz。9月12日の午前10時で解答の送信が締め切られ、有志による解答例の公開(いわゆる”晒し”)が始まっています。

ということで、私も自分の解答を”晒し”てみることにします。まずは、分野別クイズの「一人ゲーム」から。

この「一人ゲーム」のルールは、

• 問題として10個以下の整数が渡される
• プレイヤーは
  • 全ての5の倍数(0を含む)を取り除く
  • 全ての数字を半分にする(端数切り捨て)

  のどちらかの操作ができる。

• 問題の整数が全て取り除かれれば終了
• 終了までの最短の操作回数を答える

というもの。

例えば問題として、

10　11

の2つの整数が渡された場合、

10　11　―(取る)→　11　―(半分)→　5　―(取る)→　終了　なら3手
10　11　―(半分)→　5　5　―(取る)→　終了　なら2手

なので、答えは「2」となります。

問題のファイルは、先頭行に問題数、次の行から問題の整数の数、問題の整数のリストの繰り返しとなり、問題数は全部で100問。解答は、各行に各問題の解答の手数を書いた100行のファイルで送信します。

以下、私の解答コード。言語はPythonです。

def solve(nums, step):
	step += 1
	c = 0
	for num in nums:
		if num % 5 == 0:
			c += 1
	if c == len(nums):
		return step
	hnums = []
	for n in range(len(nums)):
		hnums.append(nums[n] / 2)
	hsteps = solve(hnums, step)
	if c > 0:
		rnums = []
		for n in range(len(nums)):
			if nums[n] % 5 != 0:
				rnums.append(nums[n])
		rsteps = solve(rnums, step)
		return hsteps if rsteps > hsteps else rsteps
	return hsteps

f = open('numbers', 'r')
r = open('result', 'w')
for q in range(int(f.readline())):
	f.readline()
	nums = []
	for num in f.readline().split():
		nums.append(int(num))
	r.write(str(solve(nums, 0)))
	r.write('\n')

コードの実行は22行目からスタートし、問題のファイルを開いて問題の整数を読み込み、solve関数を呼びます。
solve関数では、整数リストに取り除ける5の倍数があるかどうかをチェックし、全て取り除けるなら終了して手数を返します。もし数字が残るなら、全ての数字を半分にした整数リストをsolve関数に渡して再帰呼び出しし、手数を得ます(手数1)。さらに、もし取り除ける数字があった場合には5の倍数を取り除いた整数リストをsolve関数に渡して再帰呼び出しし、手数を得ます(手数2)。そして、手数1と手数2のうち、少ない手数を返します。

つまり、「取り除く」or「半分にする」の2分岐の全パターンを再帰で実行し、最も少ない手数を返すというプログラムです。最大に分岐しても2の21乗(=2097152)通り程度なので、普通のPCなら一瞬で答えが出ます。

Pythonはあまり慣れていないので、Pythonらしくないコードかもしれませんが、参考まで。

※追記
Pythonは
[n for n in nums if n % 5 != 0]
って書き方ができるんですね。

多少Pythonらしくなるように書き直してみました。

def solve(nums, step):
	step += 1
	rnums = [n for n in nums if n % 5 != 0]
	if len(rnums) == 0:
		return step
	hsteps = solve([n / 2 for n in nums], step)
	if len(rnums) != len(nums):
		rsteps = solve(rnums, step)
		return hsteps if rsteps > hsteps else rsteps
	return hsteps

if __name__ == "__main__":
	f = open('numbers', 'r')
	r = open('result', 'w')
	for q in range(int(f.readline())):
		f.readline()
		r.write(str(solve([int(num) for num in f.readline().split()], 0)))
		r.write('\n')

※追記2
最短の解を見つけるなら、幅優先探索の方が有利なんですね。
後出しになりますが、幅優先に書き直し。

def solve(anums):
	current = [anums]
	step = 0
	while 1:
		step += 1
		next = []
		for nums in current:
			rnums = [n for n in nums if n % 5 != 0]
			if len(rnums) == 0:
				return step
			if len(rnums) < len(nums):
				next.append(rnums)
			next.append([n / 2 for n in nums])
		current = next

if __name__ == "__main__":
	f = open('numbers', 'r')
	r = open('result', 'w')
	for q in range(int(f.readline())):
		f.readline()
		r.write(str(solve([int(num) for num in f.readline().split()])))
		r.write('\n')