Google Code Jam勉強会 第一回

Google Code Jam（GCJ）の勉強会に参加しました。講師はおなじみ id:chokudai 先生。
簡単な説明の後で、二問実習し、問題の後にchokudaiさんのライブコーディング、という流れ。
ちなみに二回目が4/19 18:30〜に予定されていますよ。

説明と方針

以下、chokudaiさんの解説まとめ。

GCJ用の特別な対策は基本的には必要ない。TopCoderとの違いは、時間制限が長いこと、入出力がファイルであること、実行環境がローカルであること、使える言語が自由であること。言語は自由だが処理速度の差が出るので必ず計算量を意識するべし。

各問、SmallとLargeの二種類のデータセットがある。それぞれダウンロードして4分/8分以内に結果を提出しなければならない。Largeは実行に時間がかかるので、ナイーブな実装では間に合わないことがある。
Smallを正解すると10ポイント、Largeで23ポイントが与えられる。Smallは何回も試せるが、Largeは一回しかできないので注意。
33点が予選ラウンド通過スコアなので、Largeを一問解けば（Smallも解けるので）通過できる。逆にSmallが三問解けても点数が足りない。Largeをしっかり一問解けるかどうかが鍵。

そして実習へ。

GCJ Africa and Arabia 2011 Qualification Round A. Closing the Loop

赤と青のロープを交互に結び合わせて輪を作る。結び目の箇所には両方のロープ合わせて1cmを使う。与えられた長さと本数がまちまちのロープから最大何cmの輪を作れるか、という問題。
GCJの問題は初めてだったので入力の書き方をどうするか悩みながらも、問題自体は特に問題なく解けた。赤と青の本数の小さい方を取り、その本数分、長いロープから使っていく。

import sys
def readline():
    return sys.stdin.readline().strip()

num_case = int(readline())
for i in range(num_case):
    red_lopes = []
    blue_lopes = []
    num_lope = int(readline())
    lopes = readline().split()
    for lope in lopes:
        color = lope[-1]
        length = int(lope[:-1])
        if color == 'R':
            red_lopes.append(length)
        else:
            blue_lopes.append(length)
    red_lopes = sorted(red_lopes)
    red_lopes.reverse()
    blue_lopes = sorted(blue_lopes)
    blue_lopes.reverse()
    num_used = min(len(red_lopes), len(blue_lopes))
    len_knots = num_used * 2
    len_lopes = sum(red_lopes[:num_used]) + sum(blue_lopes[:num_used])
    print 'Case #%s: %s' % (i+1, len_lopes - len_knots)

GCJ 2010 Qualification Round C. Theme Park

ローラーコースターがR回運行する。一度に乗せられる人数はk人。乗客はN個のグループが並んでおり、同じグループの人はまとめて乗せなければならない。また、順番を飛ばすこともできない。つまり、k=5の時に、{2, 2, 3, 1}人ずつのグループがあったとすると、最初に乗せられるのは4人。乗り終わったグループはまた列の最後に並ぶことになる。R回運行した後の運賃合計（1人1ユーロ）を答える。

LargeではRが最大10の8乗。まともにR回シミュレーションをしていると、8分以内に終わることはできない。シミュレーション中にループする箇所が出てきて、その分をまとめてスキップしてあげれば最短の時間で処理できるだろう・・・というのはすぐに思いついた。

しかし残念ながら勉強会の時間内には解けなかった。帰宅してからやっと書けたが、一度で全グループを乗せられてしまうケースへの対処に苦労した。プログラム的に難しい問題だと思う。

import sys
def rl(conv=str):
    return conv(sys.stdin.readline().strip())

num_cases = rl(int)
for i in range(num_cases):
    R, k, N = map(int, rl().split())
    groups = map(int, rl().split())
    sum_r = 0
    sum_p = 0
    index = 0
    start = 0
    starts = {}
    skiped = False
    p = 0
    while sum_r < R:
        g = groups[index]
        p += g
        index += 1
        if len(groups) == index:
            index = 0
        if k < p + groups[index] or index == start:
            sum_r += 1
            sum_p += p
            if not skiped and index in starts:
                prev_p, prev_r = starts[index]
                jump_p = sum_p - prev_p
                jump_r = sum_r - prev_r
                num_jump = (R - sum_r) / jump_r
                sum_p += num_jump * jump_p
                sum_r += num_jump * jump_r
                skiped = True
            starts[start] = (sum_p - p, sum_r - 1)
            start = index
            p = 0
    print 'Case #%s: %s' % (i + 1, sum_p)

（4/7）最初に載せたものは不要な変数やimport文が残っていたので、整理した。

ほぼ一発で動くライブコーディングはさすが。