Google Code Jam Japan 2011予選A. カードシャッフル

先週末にGCJJ2011の予選が開催されてたので，自分もちょこっとやってみました．初めてのプログラミングコンテストでいろいろ反省点はあるのですが，一番は自分のプログラミングは計算量を全く意識していないなぁということです．スケーラビリティがないというか，要はsmallが解けてもlargeが解けないよね，ということです．そのへんをもう少し考慮するようにコードを書きたいなぁというのが初参戦で学んだことです．あとはインプットをダウンロードしてから数分でアウトプットを入力をしなきゃいけないなど，かなりドキドキしますね．．．

A問題カードシャッフルはこういう問題でした．
http://code.google.com/codejam/contest/dashboard?c=889487

ということで，自分のヘボいコードを晒します．

#! c:/Python27/python.exe
# -*- coding: utf-8 -*-

input  = 'A-large.in'
output = 'gcjj2011_0A_output-large.txt'

def step(list, A, B):
    top = list[(A-1):(A+B-1)]
    list[(A-1):(A+B-1)] = []
    list = top + list
    return list

if __name__ == '__main__':
    f = open(input)
    fout = open(output,'w')

    a = int( f.readline() )
    for i in range(a):
        line = f.readline().split()
        M = int(line[0])
        C = int(line[1])
        W = int(line[2])
        print M, C, W
        list = range(M)
        for j in range(C):
            line2 = f.readline().split()
            A = int(line2[0])
            B = int(line2[1])
            print A, B
            list = step(list, A, B)
            print list
        #print list[W-1] + 1
        print "Case #"+str(i+1)+": " + str(list[W-1] + 1)
        fout.write("Case #"+str(i+1)+": " + str(list[W-1] + 1) + '\n')
    fout.close()

とりあえず何も考えずに手順通り書いてみたんですね．もうアルゴリズムもクソもなく，ただの手順通り…．で，smallをダウンロードして回してみると特に問題なく答えが得られました．なーんだ，余裕じゃんと思ってlargeをダウンロード．今考えるとここが本当にバカでした．largeは1回切り，つまり1回しか回答できない上に，一度ダウンロードすると8分以内に回答しなきゃいけないんです．そんなことも知らずにインプットをダウンロードし，プログラムを回してみる．

すると，うぉーんというけたたましい音がPCから鳴り響き，さきほどは1秒もかからずに結果が出てきたのに結果が出てくる気配もない．まぁlargeだし問題数が多いんだろう．仕方ないかーと思って待ってるんですが，いつまで経っても終わる気配なし．あれ？っと思ってコンソール見ると，7問目までは普通に回答してるのに8問目で止まっている．ここでようやく事の重大さに気付くわけです．「あ，largeって問題数が多いんじゃないんだ…」そして，おそるおそるinputファイルを見てみると，カードの枚数が1000000000枚とかあるわけですよ．それを馬鹿正直にシャッフルしてるわけですよ，オレ．で，メモリみると8GBとか使ってるわけです．バカですよね…．で，そうこうしてるうちに8分は経過し，largeはアウトに…．なるほど，largeって問題数が多いよという意味ではなく，アホな書き方をするとメモリが足りなくなるということなのですね．いや，もうアホかと．

で，しくしく書き直したのがこちら．

#! c:/Python27/python.exe
# -*- coding: utf-8 -*-

input  = 'A-large.in'
output = 'gcjj2011_0A_output-large.txt'

def step(M,C,W,A,B):
    for i in range(C)[::-1]:
        if W <= B[i]:
            W = A[i] + W - 1
        elif W <= A[i] + B[i] - 1:
            W -= B[i]
    return W

if __name__ == '__main__':
    f = open(input)
    fout = open(output,'w')

    a = int( f.readline() )
    for i in range(a):
        line = f.readline().split()
        M, C, W = int(line[0]), int(line[1]), int(line[2])
        A, B = [], []
        for j in range(C):
            line2 = f.readline().split()
            A.append(int(line2[0]))
            B.append(int(line2[1]))
        #print M, C, W, A, B
        print "Case #"+str(i+1)+": " + str(step(M,C,W,A,B))
        fout.write("Case #"+str(i+1)+": " + str(step(M,C,W,A,B)) + '\n')
    fout.close()

これなら一瞬で解けます．ということで教訓は普段ならともかくプログラミングコンテストで富豪的プログラミングをするなという当然のお話でした．あ，ちなみに本戦には当然いけてません．しょぼーん，ただGDD2011の参加証が本日届いたので，まぁいいかという感じですｗ