午後から→オーバークロック

駆け出しハッカー()によるプログラミング・サービス開発備忘録。

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つに分けて考える。
    • 12345を321(123を逆順にしたもの)と45に分ける。
    • 前半:10000->10321を数え上げる。321-0+1=321。この後10321をreverseして12301を得る。
    • 後半:12301->12345を数え上げる。45-1+1=45。
    • よって、10000->12345を数え上げると321+45=366。
  • 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シャツ欲しいので次がラストだけど頑張るしかない!!