naoya_t@hatenablog

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

Google Code Jam Practice Session 2018

Google Code Jamのpractice session。
今年から(ローカル実行ではなく)サーバ上での実行になる(のでデータをダウンロード/アップロードする手間はなくなるが、用意されている言語しか使えなくなる?)

practiceの問題は過去問から取られている。

今回は(testing_pool.pyにつられて)全部Python3で書いた。

f:id:n4_t:20180402080530p:plain

Number Guessing (interactive)

インタラクティブな数あてゲーム。数を1つ言うと、正解・大きすぎ・小さすぎ、のどれかを返してくるからそれをヒントに正解を探る。
インタラクティブなテストスクリプト(testing_pool.py)が用意されているけれど、Chromeでは警告が出てダウンロードできなかった。代わりにSafariで。

普通に二分探索で。
AC

import sys

def read_ints(check=None):
    ints = [int(x) for x in sys.stdin.readline().rstrip().split(' ')]
    if check:
        assert len(ints) == check
    return ints

def read_int():
    return read_ints(check=1)[0]

def ask(x):
    sys.stdout.write('%d\n' % x)
    sys.stdout.flush()

    res = sys.stdin.readline().rstrip()
    if res == 'CORRECT':
        return 0
    elif res == 'TOO_SMALL':
        return -1
    elif res == 'TOO_BIG':
        return 1
    else:
        assert False

def solve(A, B, N):
    # sys.stderr.write('solve: (%d, %d], within %d guess\n' % (A, B, N))
    while A < B:
        # (a, B]
        # sys.stderr.write('  (%d, %d], within %d guess\n' % (A, B, N))
        m = (A + B + 1)//2
        p = ask(m)
        if p < 0:
            # too small
            A = m
        elif p > 0:
            # too large
            B = m-1
        else:
            return
        N -= 1

def main():
    T = read_int()
    for t in range(T):
        A, B = read_ints(2)
        N = read_int()
        solve(A, B, N)

if __name__ == '__main__':
    main()

Senate Evacuation

議員会館で火災が発生。上院議員たちを避難させたいが、出口は1度に2人ずつしか通れない。避難中に議決が必要な事態が発生する可能性を考慮し、いずれかの党のメンバーが残っている議員の過半数を占めることのないように計画して外に出していきたい。

逆順に考える。党員数を降順に並べて、上位2党から1人ずつ選んでペアにする。こういうペアがいくつ集まっても、どこかの党が過半数を取ることはない。ペアが組めない時〈残り人数が奇数)は1人で。というのを逆順に言えばいい。
priority_queueを使った実装。
AC

import sys
from queue import PriorityQueue

def read_ints(check=None):
    ints = [int(x) for x in sys.stdin.readline().rstrip().split(' ')]
    if check:
        assert len(ints) == check
    return ints

def read_int():
    return read_ints(check=1)[0]

def solve(N, P):
    pq = PriorityQueue()
    for i, pi in enumerate(P):
        c = chr(0x41 + i)
        pq.put( (-pi, c) )

    q = []
    while not pq.empty():
        _p, c = pq.get()
        pi_c = -_p
        if pq.empty():
            q.append(c)
            pi_c -= 1
            if pi_c > 0:
                pq.put( (-pi_c, c) )
        else:
            _p, d = pq.get()
            pi_d = -_p
            q.append(c+d)
            pi_c -= 1
            if pi_c > 0:
                pq.put( (-pi_c, c) )
            pi_d -= 1
            if pi_d > 0:
                pq.put( (-pi_d, d) )
    print(' '.join(q[::-1]))

def main():
    T = read_int()
    for t in range(T):
        N = read_int()
        assert 2 <= N <= 26

        P = read_ints(check=N)
        assert sum(P) <= 1000

        sys.stdout.write('Case #%d: ' % (1+t,))
        solve(N, P)

if __name__ == '__main__':
    main()

Steed 2: Cruise Control

道を先行する馬たちの位置と速度が分かっていて、それを追い抜くことなくなるはやで到着したい。

いちばん遅く到着する馬の到着に合わせてゴールできるような速度で行けばいい。
AC

import sys

def read_ints(check=None):
    ints = [int(x) for x in sys.stdin.readline().rstrip().split(' ')]
    if check:
        assert len(ints) == check
    return ints

def read_int():
    return read_ints(check=1)[0]

def solve(D, N, ks):
    a = []
    for ki, si in ks:
        ai = (D - ki)/si
        a.append(ai)
    v = D / max(a)
    return v

def main():
    T = read_int()
    # sys.stderr.write('T=%d\n' % T)
    for t in range(T):
        D, N = read_ints(2)
        ks = []
        for l in range(N):
            Ki, Si = read_ints(2)
            ks.append( (Ki, Si) )

        v = solve(D, N, ks)
        sys.stdout.write('Case #%d: %.6f\n' % (1+t, v))

if __name__ == '__main__':
    main()

Bathroom Stalls

横一列に並んだ浴室に鴨川等間隔の法則で1人ずつK人が入っていったとき、K人目の左右の連続空き室数を求める。

データセットが小(N≦1e3)・中(N≦1e6)・大(N≦1e18)とある。
大きなセットまではシミュレーションでは無理。

いまあいてる区間、をpriority_queueに突っ込んで、(幅-1)を左右に分けてそれぞれをまた突っ込む。
同じ長さの区間はまとめる(キューのtopと同じ幅だったらそいつとまとめる)。
priority_queueに入れるのは (width, count) だけど、widthの大きい順に取り出したいのでPythonのqueue.PriorityQueueの場合-widthとする。
この時count人がその幅の状況で浴室に入る。最初からやっていってK人目が入る回に、max(左,右), min(左,右) を返す。
O(logN) というか O(logK)。
AC

import sys
from queue import PriorityQueue

def read_ints(check=None):
    ints = [int(x) for x in sys.stdin.readline().rstrip().split(' ')]
    if check:
        assert len(ints) == check
    return ints

def read_int():
    return read_ints(check=1)[0]

def solve(N, K):
    pq = PriorityQueue()
    pq.put( (-N, 1) )

    entered = 0
    while not pq.empty():
        _n, cnt = pq.get()
        n = -_n

        if not pq.empty():
            _n2, cnt2 = pq.get()
            if _n2 == _n:
                cnt += cnt2
            else:
                pq.put( (_n2, cnt2) )

        # print('(%d %d) %d -> %d' % (n, cnt, entered, entered+cnt))

        left = (n-1) // 2
        right = (n-1) - left

        if K <= entered + cnt:
            # print('HERE')
            return max(left, right), min(left, right)

        entered += cnt

        if left == right:
            if left > 0:
                pq.put( (-left, cnt*2) )
        else:
            if left > 0:
                pq.put( (-left, cnt) )
            if right > 0:
                pq.put( (-right, cnt) )

    return 0, 0

def main():
    T = read_int()
    for t in range(T):
        N, K = read_ints(2)
        y, z = solve(N, K)
        sys.stdout.write('Case #%d: %d %d\n' % (1+t, y, z))

if __name__ == '__main__':
    main()