「オフラインリアルタイムどう書くF06の問題 - ツリーの中の数」の解答
http://nabetani.sakura.ne.jp/hena/ordf06numit/
会場では残り20分ぐらいのときに出来上がりましたが、
「メモ化」というテクニックを知らず非常に効率の悪いもので、実行終了まで十数分要するものでした。
以下は、会場で得た新しいスキル「メモ化」を適用後のコード。
一瞬で終わるようになりました。
その他に以下を実施しています。
- 再帰処理の見直し
- グローバル変数廃止
- '/'を'//'に置き換え
main.py
def right_func(input_num):
return input_num // 2 - 10
def left_func(input_num):
return input_num * 2 // 3
def calc(memo, input_num, target):
if input_num in memo:
return memo[input_num]
if input_num < target:
return 0
if input_num == target:
return 1
ans = calc(memo, right_func(input_num), target) + calc(memo, left_func(input_num), target)
memo[input_num] = ans
return ans
def resolve(data):
memo = {}
split = data.split(",")
input_num = int(split[0])
target = int(split[1])
return str(calc(memo, input_num, target))
## test logic
class Result:
def __init__(self):
self.success = 0
self.fail = 0
RESULT = Result()
RESULT.success = RESULT.fail = 0
def test(data, expect):
print("actual:" + resolve(data) + " expected:" + expect)
if resolve(data) == expect:
RESULT.success += 1
else:
RESULT.fail += 1
test( "123,4", "5" )
test( "1,1", "1" )
test( "2,1", "1" )
test( "3,3", "1" )
test( "19,5", "1" )
test( "69,5", "3" )
test( "88,9", "2" )
test( "1,100", "0" )
test( "100,4", "4" )
test( "101,9", "0" )
test( "456,7", "7" )
test( "567,8", "12" )
test( "756,10", "10" )
test( "789,10", "12" )
test( "896,29", "2" )
test( "7764,6", "664" )
test( "1234,56", "3" )
test( "8563,29", "35" )
test( "12345,67", "10" )
test( "72927,51", "263" )
test( "71441,145", "22" )
test( "123456,78", "397" )
test( "123456,789", "1" )
test( "592741,216", "55" )
test( "913826,584", "81" )
test( "1234567,89", "2293" )
test( "10000000,1", "19383507" )
test( "12345678,9", "3567354" )
test( "6215879,358", "2907" )
test( "12345678,90", "79419" )
test( "5745432,1032", "1287" )
print("Success: {0.success}, Fail: {0.fail}".format(RESULT))