Google Code Jam Japan 2011決勝

113位でGoogle T-shirtsゲットです！！Aが早く解けてしまって、暫く10位台だったので、かなり興奮してましたが、その後何もできませんでした。BとCトライしましたが、WAでした。やったことを書きます。

A. アンテナ修復

　角度が等しいので、三角形の面積は辺の長さによってのみ決まります。長い辺同士を掛けた方がお得なので、greedyに入れて行きます。アンテナが円の形をしているので、双方向キュー（STLのdeque）を使って実装しました。本番は直観のまま突き進んで、今回は運よくACだったけど、証明せずにsubmitっていうのはあまりよくない習慣です。ちょっと証明を考えてみました。

　一番長いエレメントをx1, 二番目に長いエレメントをx2とおく。このとき、私の解法では最適解においてx1 * x2の項が存在しています。これを背理法で証明してみます。

もし、x1*x2の項がないと仮定する。このとき、ある項xp * xqのxqとx2を交換する。すると、x1*xq、xp*x2という項ができる。もとの最適値に対して、この解は、-(x2 - xq) * x1 + (x2- xq) * xp = (-x1 + xp) (x2 - xq)だけ変化したことになります。この変化分は負なので、x1*x2という組み合わせは最適値に含まれます。

以下同様にしてgreedyにとっていけばOKです。

B. バクテリアの増殖

　ただの繰り返し二乗法じゃない？と思ってやったけど最後のサンプルがあわない。何度やってもあわない。Aの採点方式が間違っているというアナウンスがあったため、Bのサンプルおかしいんじゃない？と疑いだす始末。暫くしてレッドコーダーの人達がACし出すので、おそらく何か勘違いしてるんだろうなと思いだす。コンテスト終わって、modのところで大きな勘違いをしているのに気付きました。

　A ^p (mod N)　は、 A^(p mod N) (mod N)とは違いますね。。何やってんだか。。この問題、オイラーの定理使って周期出すだけじゃんと思いましたが、AとCがco-primeじゃない場合もあるので、難しいですねー。。十分に大きな値に対してはφ関数の値が周期になるはずなので、これを使えばいいっぽいです。十分に大きなって微妙な表現だけど、どれくらい大きければいいかは数論の本を見て復習しなければ・・。

C. ワイルドカード

　largeは諦めて、small狙いでいきました。単純な全探索でいいのですが、C++で正規表現関数を自作して、sampleは何とか通せたけど、submitしたらWA食らいました。暫くバグ取りと格闘して、Pythonでやろうと迷いましたが、暫くPython書いてないので頑張ってC++でごりごりやってたら時間切れ。言語によって差が出てしまうような問題はあまり好きじゃないですが、問題に応じて適切な言語を使うことができるのも技術者として重要な能力の一つと考えれば文句は言えません。

　コンテスト後、Pythonで復習しました。

import re

def smaller(x, y):
    if len(x) < len(y):
        return True
    if len(x) > len(y):
        return False
    if x.count("*") < y.count("*"):
        return True
    if x.count("*") > y.count("*"):
        return False
    return x < y

def solve():
    A = raw_input()
    B = raw_input()
    
    ret = "*" * 1024;
    L = len(A)
    for mask in range(1<<L):
        At = ""
        for i in range(L):
            if (mask >> i & 1):
                At += A[i]
            else:
                if len(At) == 0 or At[-1] != '*':
                    At += "*"
            
        if not re.match("^" + At.replace("*", ".*") + "$", B):
            if smaller(At, ret):
                ret = At
           
    return ret        

T = int (raw_input())
for t in range(T):
    print "Case #%s: %s" % (t+1, solve())