読者です 読者をやめる 読者になる 読者になる

唯物是真 @Scaled_Wurm

プログラミング(主にPython2.7)とか機械学習とか

Google code jam 2015 Round 1C ◯◯△

競技プログラミング

277位、77点
なんとか今年もRound1を通過出来ました

Problem A. Brattleship

配置された戦艦の場所を当てるゲームを行う
行が\(R\)個、列が\(C\)個の盤面で、大きさ\(1 \times W\)の戦艦がひとつ配置される
戦艦は水平線方向が長くなるような向きでしか配置できない

こちらが場所を指定して攻撃すると戦艦に当たったかどうかを教えてくれる
ただし相手はいつでもチートをして過去の当たったかどうかの情報に矛盾がない範囲で戦艦を移動することができる
戦艦のすべての位置に当たるまでに必要な回数の最小値を答える

\(W\)個ずつ距離をとって攻撃していくと最後には必ず戦艦に当てることができる(\(\lfloor C/W \rfloor \times R\)回必要)
後は当たった箇所がちょうど盤面の端だったら\(W - 1\)回、そうでなければ\(W\)回の攻撃で戦艦のすべての位置に攻撃できる

T = input()

for t in xrange(T):
    R, C, W = map(int, raw_input().split())
    
    d = C / W
    
    result = d * R + W
    
    if C % W == 0:
        result -= 1
    
    print 'CASE #{}: {}'.format(t + 1, result)

Problem B. Typewriter Monkey

\(K\)種類のキーボードのキーの文字と長さ\(L\)の目的の文字列が与えられる
猿がランダムにキーボードを叩いて\(S\)文字打つ
\(S\)文字に連続して含まれる目的の文字列の数だけ猿にバナナを与える("AAA"には"AA"が2回含まれていると数える)
猿に与える可能性があるバナナの数の最大値 マイナス バナナの数の期待値を答える

猿に与える可能性があるバナナの最大値は、一部が重複する場合を考慮して長さを割れば求められる
ある場所から目的の文字列が始まる確率は対応した文字の確率をかけ合わせればよく、この確率を\(p\)とする
バナナの数の期待値は、期待値の線形性から可能なすべての位置での期待値を足し合わせればよいので\(p \times (S - L + 1)\)

import collections

T = input()

for t in xrange(T):
    K, L, S = map(int, raw_input().split())
    key = raw_input()
    target = raw_input()
    
    L = len(target)
    
    diff = L
    for i in xrange(1, L):
        temp = target[i:]
        if temp == target[:len(temp)]:
            diff = i
            break
    
    count = collections.Counter()
    for k in key:
        count[k] += 1
    for k in count:
        count[k] /= float(K)
    
    prob = 1.0
    for s in target:
        prob *= count[s]
    
    if S >= L and prob != 0.0:
        BANANA = float((S - L) / diff + 1)
    else:
        BANANA = 0.0
    
    pay = 0.0
    if S >= L:
        pay = prob * (S - L + 1)
    result = BANANA - pay
    print 'CASE #{}: {}'.format(t + 1, result)

Problem C. Less Money, More Problems

\(D\)種類の額面のコインと同じ種類のコインを使える枚数の最大値\(C\)が与えられる
\(V\)までの正の整数の金額をすべて支払えるようにするためには、後何種類のコインを追加する必要があるか最小値を答える

largeの解法はわからなかった
smallはごり押しで全部のコインを使った場合の金額をそれぞれ出して、金額の低い方から見ていって作れていなかったらその金額のコインを足していったら何故かうまくいった

import itertools

T = input()

for t in xrange(T):
    C, D, V = map(int, map(int, raw_input().split()))
    coin = map(int, map(int, raw_input().split()))
    
    possible = [0] * (V + 1)
    possible[0] = 1
    
    for i in xrange(1, D + 1):
        for c in itertools.combinations(coin, i):
            s = sum(c)
            if s <= V:
                possible[s] = 1
    
    result = 0
    for i in xrange(V + 1):
        if possible[i] == 0:
            result += 1
            for j in xrange(V, -1, -1):
                if possible[j] == 1 and j + i <= V:
                    possible[j + i] = 1 
    
    print 'CASE #{}: {}'.format(t + 1, result)

C-largeを解いたので追記
コインを金額の小さい順に試していって、あるコインまでのときその金額までの間に払えない金額がない金額の最大値を\(X\)とすると\(X+1\)の金額のコインを足すことで\(X + C(X + 1)\)まで払えるようになる
この手順をコインが必要な箇所だけ繰り返していけばよい
新しい種類のコインを追加するとき、作れる金額は少なくとも\(2\)倍以上になるので\(V\)が大きくても\(O(\log V)\)で計算できる

T = input()

for t in xrange(T):
    C, D, V = map(int, map(int, raw_input().split()))
    coin = map(int, map(int, raw_input().split()))
    
    coin.sort()
    result = 0
    ok = 0
    
    if coin[0] != 1:
        result += 1
        coin = [1] + coin
    
    coin.append(V + 1) #sentinel value
    
    for c in coin:
        while c > ok + 1 and V > ok:
            result += 1
            ok += (ok + 1) * C
        if V <= ok:
            break
        ok += c * C
    
    print 'CASE #{}: {}'.format(t + 1, result)
-->