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')