Google Code Jam Round1B - Problem A. Counter Culture - in Python
Google Code JamのRound1Bで憤死(0完)しましたが悔しいので時間外でA,Bを解いてみる。
どうやらBは2パターンの市松模様を試せばそれで良いっぽいので、今回はAだけ書きました。
ProblemA. Counter Culture
full search
時間内ではいきなり最適解を出そうと頑張って、結局smallさえ通せなかったので、
とりあえず総当たりで解きます。
dp = [0 for i in xrange(1000001)] for i in xrange(1,1000001): if dp[i] == 0: dp[i] = dp[i-1] + 1 reverse = int(str(i)[::-1]) if dp[reverse] == 0: dp[reverse] = dp[i] + 1 else: if dp[i] > dp[i-1] + 1: dp[i] = dp[i-1] + 1 t = input() for _ in xrange(t): n = input() print "Case #%d: %d" % (_+1,dp[n])
総当たりといってもテストケース100個に対して毎回106を計算するのも微妙なので、
最初にDPテーブルを作ってから解きます。
optimize
時間内で解いた時に検討した解法は以下。
例えばInputが12345だとすれば、
- 1->12345をいきなり数えるのではなく、1->9,10->99,100->999,1000->9999,10000->12345に分けて考える。
- 10000->12345を解く時は前半と後半2つに分けて考える。
- 10->99,100->999,1000->9999についても同様にアプローチして、全てを合計すると解が求まる。(1->9だけは数え上げ)
この方針で解を出して、smallの出力とopendiffでdiffを取ってみると、
例えば990000の時にうまくいってないことがわかった。
確かに、100000->100099->990001->990000となり、reverseする前の手順で数えすぎなことがわかる。
仕方ないので、後半部分の数字が0の場合だけ、Input-1の答え+1を返すようにした。
(Inputが990000の場合は989999の答え+1)
最終的なコードは以下。
# return answer def answer(x): ans = 0 for i in xrange(1,len(str(x))+1): if i == len(str(x)): ans += count(10 ** (i-1),x) else: ans += count(10 ** (i-1),10 ** i - 1) return ans # return a number to change x to y(len(x) == len(y)) def count(x,y): leny = len(str(y)) if leny == 1: #print "x:%d,y:%d,ans:%d" % (x,y,y-x+1) return y - x + 1 # when y == 12345, front_half == 321 and back_half == 45 front_half = int(str(y)[::-1][leny/2:]) back_half = int(str(y)[(leny-leny/2):]) ans = 0 if back_half != 0: ans += front_half - int(str(x)[(leny/2):]) + 1 ans += back_half - int(str(x)[::-1][(leny-leny/2):]) + 1 else: return 1 + count(x,y-1) #print "x:%d,y:%d,f:%d,b:%d,ans:%d" % (x,y,front_half,back_half,min(ans,y-x+1)) return min(y-x+1,ans) t = input() for _ in xrange(t): n = input() #print "Input #%d: %d" % (_+1,n) print "Case #%d: %d" % (_+1,answer(n))
今回のケースで改めてsmallを先に解く戦法の重要性を知った。
(じゃないと990000などのうまくいかないケースを発見できなかったと思う)
Tシャツ欲しいので次がラストだけど頑張るしかない!!