Google code jam 2013 Round 1 C ◯△△

A、B、CのsmallとAのlargeを正解。
1000人までが次のラウンドに通過できるんですが、447位でした。
ここ数年は毎年挑戦してるんですが初めてRound 2に行けました(弱

Problem A. Consonants

部分文字列中で子音(aeiou)がn文字以上連続で登場するものの個数を答える。
ただし、まったく同じ文字列でも位置が違えば別のものとみなす。

解法

文字列の最大長さが $10^6$ なのですべての始点と終点について試すのは計算量的に無理。

文字列中に子音がn文字以上連続している場所をxと呼ぶ。
xが一箇所の場合、その左端より左のすべての位置(端を含む)の長さと右端より右のすべての位置(端を含む)までの長さをかけあわせればよい。
複数ある場合には、一個目は一箇所しかない場合と同様。
二個目以降はその左端からすでに計算済みのxまでの長さと右端より右の長さ(端を含む)をかけあわせればよい。

ソースコード

import sys

T = int(raw_input())
vowel = list('aeiou')
for i in xrange(1, T + 1):
    s, n = raw_input().split()
    n = int(n)
    
    last = -1
    index = 0
    count = 0
    length = len(s)
    add = 0
    for c in list(s):
        if c not in vowel:
            count += 1
            if count >= n:
                left = (index - n + 1) - last
                right = length - index
                add += left * right
                last = index - n + 1
        else:
            count = 0
        index += 1
    print "Case #{0}: {1}".format(i, add)

Problem B. Pogo

それぞれのターンに1, 2, 3, 4, 5, ..., nと上下左右に移動できるときに目的地に到達できる最短経路を答える。
ただしsmallについては最短でなくてもよく500ターン以内であればよい。

解法

smallは $|X|, |Y| \leq 100$ なので「東西」とか「北南」とかで2ターンかけて1マスずつ移動していっても余裕で間に合うので、探索とかはする必要がない。
smallしか解けず。

Twitterで見かけたlargeの解法。

GCJ Round1CのBは、去年のAutumn FestのE問題とほとんど同じなのでこれを理解していたら楽勝のはず URL

2013-05-12 20:30:28 via Twitter for Mac

ソースコード

smallだけ

import sys

T = int(raw_input())
for i in xrange(1, T + 1):
    x, y = map(int, raw_input().split())
    route = ''
    while x != 0:
        if x > 0:
            route += 'EW'
            x -= 1
        else:
            route += 'WE'
            x += 1
    while y != 0:
        if y > 0:
            route += 'NS'
            y -= 1
        else:
            route += 'SN'
            y += 1
    print "Case #{0}: {1}".format(i, route[::-1])

Problem C. The Great Wall

敵がある範囲で攻めてくる。
ある範囲の壁の高さが敵の攻撃力以下の時、攻撃は成功する。
その日の終わりに攻撃が成功した範囲の壁の高さは攻撃力の高さまで作りなおされる。
敵の位置や攻撃力、攻撃回数などが入力として与えられ、攻撃が成功した回数を答える。

解法

計算量的にsmallしかわからなかったのでlargeは諦める。
smallは与えられた範囲について毎回壁の高さを更新していって計算した。

import sys
import collections

T = int(raw_input())
for i in xrange(1, T + 1):
    N = int(raw_input())
    attack = []
    for j in xrange(N):
        d, n, w, e, s, delta_d, delta_p, delta_s = map(int, raw_input().split())
        for k in xrange(n):
            attack.append((d + k * delta_d, (w + k * delta_p) * 2, (e + k * delta_p) * 2, s + k * delta_s))
    attack.sort()
    count = 0
    before = -1
    area = collections.Counter()
    
    todo = []
    for d, w, e, s in attack:
        if before != d:
            for t_w, t_e, t_s in todo:
                for j in xrange(t_w, t_e + 1):
                    area[j] = max(t_s, area[j])
            todo = []
        for j in xrange(w, e + 1):
            if area[j] < s:
                count += 1
                todo.append((w, e, s))
                before = d
                break
    print "Case #{0}: {1}".format(i, count)