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

naoya_t@hatenablog

いわゆるチラシノウラであります

Google Code Jam 2014 - Qualification Round

GCJ予選。
27時間(日本時間で4/12朝8amから翌4/13の11amまで)のうちならいつ参加してもOK。

予選だし、外でお茶でも飲みながら参戦したいのだけれど、この直前にOS XをMavericksにバージョンアップしてしまった結果、GCCが動かない。
Python2.7は(ライブラリ類は全部入れ直しの必要がありそうだけれどGCJなら不要だし)動くっぽいのでPythonで参戦することにした。

時々行くカラオケボックス(電源が取れる所ね)で、1問解けたら1曲歌っていい、みたいなノリで問題を解き始めた。


25点で予選通過なので、A(s) + B(s) + C(s) もしくは A(s) + B(s+l) を通すのが目標。
・・・

無事、予選通過確定ライン(Smallのみで25点確保)に到達してから店を発つことが出来た。
結果、A(s) + B(s+l) + C(s+l) + D(s+l) 全部ACで90点満点(695位)。


Round 1Aでお会いしましょう。

以下、投稿コード(一応すべてAC)。

Problem A. Magic Trick

Small only, 6pts

#!/usr/bin/env python
# -*- coding: utf-8 -*-

def main():
    t = input()
    for i in range(t):
        print "Case #%d:" % (1+i),

        a1 = input()
        s1 = []
        for j in range(4):
            r = frozenset(map(int, raw_input().split()))
            s1.append(r)

        a2 = input()
        s2 = []
        for j in range(4):
            r = frozenset(map(int, raw_input().split()))
            s2.append(r)

        s = list(s1[a1-1].intersection(s2[a2-1]))

        if len(s) == 0:
            print "Volunteer cheated!"
        elif len(s) == 1:
            print s[0]
        else:
            print "Bad magician!"

if __name__ == '__main__':
    main()

Problem B. Cookie Clicker Alpha

Small: 8pts
Large: 11pts
皆さんおなじみの、クッキークリッカーにまつわる問題。

Please don't go play it now: it might be a long time before you come back.

ってのをちゃんと守りました!

#!/usr/bin/env python
# -*- coding: utf-8 -*-

def solve(c, f, x):
    # small: 1-500 1-4 1-2000
    # large: 1-10000 1-100 1-100000
    t = 0 #時刻
    # m = 0 #枚数
    v = 2.0 #初速

    best = x/v + 1
    k = 0
    while True: # m < x:
        dt_c = c/v
        dt_m = x/v

        t_ = t + dt_m
        if t_ >= best:
            return best
        best = t_

        t += dt_c
        # m = 0 #全部使っちゃうからね
        v += f
        k += 1

def main():
    t = input() # 1-100
    for i in range(t):
        c, f, x = map(float, raw_input().split())
        print "Case #%d: %.7f" % (1+i, solve(c,f,x))


if __name__ == '__main__':
    main()

Problem C. Minesweeper Master

Small: 11pts
Large: 24pts

(その1)
#!/usr/bin/env python
# -*- coding: utf-8 -*-

import copy

memo = set()
ans = {}

def key(r,c,a):
    k = 0
    mag = 1
    for ai in a:
        k += ai * mag
        mag *= (c+1)
    return k

def canonical(r,c,a,aa):
    b = copy.deepcopy(a)
    for i in range(r-1):
        if a[i] == c-1 and aa[i+1] == c:
            b[i] = c

    if aa[r-1] == c:
        b[r-1] = c
    else:
        b[r-1] = max(b[r-1], aa[r-1]-1)
    return b

def use(r,c,a):
    global ans

    aa = [0] * r
    # bb = [0] * (r+1)
    for i in range(r-1):
        if a[i] > 0:
            aa[i+1] = min(c, a[i]+1)
            # bb[i+1] = max(c, a[i]+1) - c
    aa[0] = aa[1]
    ## bb[0] = bb[1]
    total = sum(aa[:r])
    em = r*c - total
    if em not in ans:
        # ans[em] = canonical(r,c,a,aa) #copy.deepcopy(a)
        ans[em] = copy.deepcopy(aa)
        #print r,c,a,aa,total

def sub1(w,a):
    sp = 1
    while sp <= w:
        ans[w-sp] = [sp]
        sp += 1

def sub(r,c,a):
    global memo

    assert r <= c
    if r == 1: return sub1(c,a)

    k = key(r,c,a)
    if k in memo: return
    memo.add(k)

    use(r,c,a)
    for i in range(r):
        if i == 0 or a[i-1] > a[i]:
            if a[i] < c:
                a[i] += 1
                sub(r,c,a)
                a[i] -= 1

def gen(r,c):
    global memo, ans

    assert r <= c

    memo = set()
    ans = {}

    a = [1] + [0]*(r-1)
    ans[r*c-1] = copy.deepcopy(a)

    sub(r,c,a)

    #print ans


def play(r,c):
    if r < c:
        gen(r,c)
        return False
    else:
        gen(c,r)
        return True

def render(r,c,a,do_turn):
    m = []
    for j in range(r):
        m.append(['*'] * c)

    if do_turn:
        for j in range(c):
            for i in range(a[j]):
                m[i][j] = '.'
        pass
    else:
        for j in range(r):
            for i in range(a[j]):
                m[j][i] = '.'

    m[0][0] = 'c'
    for row in m:
        print ''.join(row)

def solve(r,c,m):
    # print "solve %dx%d + %d" % (r,c,m)
    do_turn = play(r,c)
    if m in ans:
        render(r,c,ans[m],do_turn)
    else:
        print "Impossible"

#solve(5,5,23)
#solve(5,5,24)
#solve(5,5,21)
#solve(3,1,1)
#solve(3,1,2)
#solve(2,2,1)
#solve(4,7,3)
#solve(4,7,27)

def main():
    t = input()
    for i in range(t):
        r,c,m = map(int, raw_input().rstrip().split(' '))
        print "Case #%d:" % (1+i)
        solve(r,c,m)

if __name__ == '__main__':
    main()
C (その2)
#!/usr/bin/env python
# -*- coding: utf-8 -*-

import copy

memo = set()
ans = {}

def gen(r,c):
    global memo, ans

    assert r <= c

    memo = set()
    ans = {}

    if r == 1:
        sp = 1
        while sp <= c:
            ans[sp] = [sp]
            sp += 1
        return

    ans[1] = [1]*1 + [0]*(r-1)

    w = 2
    while w <= c:
        # 4,6,8,10,...,2c
        ans[w*2] = [w]*2 + [0]*(r-2)
        w += 1

    if r >= 3 and c >= 3:
        w = 3
        while w <= c:
            # 9,11,13,
            if (w*2+3) not in ans:
                ans[w*2+3] = [w]*2 + [3]*1 + [0]*(r-2-1)
            w += 1

    h = 2
    while h < r:
        w = 2
        while w <= c:
            if (c*h+w) not in ans:
                ans[c*h+w] = [c]*h + [w]*1 + [0]*(r-h-1)
            w += 1
        if h > 2 and (c*h+1) not in ans:
            ans[c*h+1] = [c]*(h-1) + [c-1]*1 + [2]*1 + [0]*(r-h-1)
        h += 1


def play(r,c):
    if r <= c:
        gen(r,c)
        return False
    else:
        gen(c,r)
        return True

def render(r,c,a,do_turn):
    m = []
    for j in range(r):
        m.append(['*'] * c)

    if do_turn:
        for j in range(c):
            for i in range(a[j]):
                m[i][j] = '.'
        pass
    else:
        for j in range(r):
            for i in range(a[j]):
                m[j][i] = '.'

    m[0][0] = 'c'
    for row in m:
        print ''.join(row)

def solve(r,c,m):
    # print "solve %dx%d + %d" % (r,c,m)
    do_turn = play(r,c)
    sp = r*c - m # スペース
    if sp in ans:
        render(r,c,ans[sp],do_turn)
    else:
        print "Impossible"


def main():
    t = input()
    for i in range(t):
        r,c,m = map(int, raw_input().split(' '))
        print "Case #%d:" % (1+i) #, (r,c,m)
        solve(r,c,m)

if __name__ == '__main__':
    main()

Problem D. Deceitful War

Small: 14pts
Large: 16pts

import copy

def war(naomi_, ken_):
    naomi = copy.deepcopy(naomi_)
    ken = copy.deepcopy(ken_)
    naomi.sort()
    ken.sort()
    nsc = 0
    ksc = 0
    for n in naomi:
        kch = -1
        for i, k in enumerate(ken):
            if k < n: continue
            kch = k
            ken[i] = -1
            break
        if kch >= 0:
            ksc += 1
        else:
            nsc += 1

    return nsc

def deceitful_war(naomi_, ken_):
    naomi = copy.deepcopy(naomi_)
    ken = copy.deepcopy(ken_)
    naomi.sort()
    ken.sort()

    n = len(naomi)
    for t in range(n):
        w = 0
        for i in range(n):
            if naomi[i] > ken[i]: w += 1
        if w == n:
            return w
        naomi = naomi[1:]
        ken = ken[:-1]
        n -= 1

    return 0

def main():
    T = input()
    for t in range(T):
        N = input()
        naomi = map(float, raw_input().split(' '))
        ken   = map(float, raw_input().split(' '))
        # print naomi, ken
        w = war(naomi, ken)
        dw = deceitful_war(naomi, ken)
        print "Case #%d: %d %d" % (1+t, dw, w)

if __name__ == '__main__':
    main()