BLOGサブスレッドの日常

2016.04.11

Google Code Jam 2016 Qualification Round

tama

この週末は GCJ2016 こと Google Code Jam 2016
Qualification Round(QR)が開かれていました。
いい機会なので今日はGCJの紹介とGCJ2016-QRの振り返りをしてみたいと思います。

Google Code Jam とは

Googleが毎年1回開催している競技プログラミングのイベントです。(毎年いくつかのバリエーションが年数回ありますが本戦は年1回だけです)

競技プログラミング というのは一定の時間以内に決まったお題のプログラムを作るイベントで、
topcoderAtCoder など様々な大会があります。
Google Code Jam(以下GCJ)はその名の通りGoogleが開催しているものです。

GCJはプログラム言語の指定はなく、自分の手元でプログラムを実行し、
お題に沿った入力データに対応した答え(出力データ)を規定時間以内にGoogleサーバに送ることで
正誤判定されます。
ほかの競技プログラミング大会では、決められた言語(1種類とは限らない)でコードを書き、
サーバがそれを実行して速度や正誤判定をする場合もあります。
競技プログラミングごとに主旨やルールが違うので、ここではGCJに絞って紹介します。
過去問 が公開されているので
興味がある方はここを見ながら読んでいただくと少しはわかりやすいかも)

  • GCJは一度の大会で複数の問題(たいてい3〜5問)が出題されます
    • 各問題は独立していて関連性はなく、どの問題から解いてもかまいません
  • 問題ごとにストーリーがあり、何をすべきかが語られています(が問題を解く上で本質には関係ありません)
    • (ストーリー風でなくやや数学、プログラム寄りの書き方で)細かいルールも載っています
  • 各問題で Small inputLarge input と呼ばれる2種類の入力データを解きます
    • ときどき Small input だけで Large input のない問題(GCJ2014-1A C.)や、
      Large input がふたつある問題(GCJ2013-QR C.)もあります
    • 入力データごとに正解時の獲得ポイントが決まっています(大会全体で合計100ptくらい)
  • 入力データの仕様と回答すべき出力データの仕様、入力値の制限が定められています
    • 入力値の制限は例えば入力データセット数であったり、各値の上限値だったりします
      • 例えば Small input の場合は 1≦N≦1000、Large input の場合は 1≦N≦1010 みたいな
  • 例題として入出力サンプルが示されています

Small inputLarge input があるのがGCJ独特かもしれません。

  • Small input

    • 入力データをダウンロードしてから4分以内に回答データとそれを算出したプログラムを送る必要があります
    • 即座に正誤判定され、回答が間違っていたり制限時間以内に回答データを送れなかった場合は wrong try としてペナルティを受けます
    • 正解するまで何度でも挑戦することができます
  • Large input

    • Small input を正解すると挑戦できるようになります
    • 制限時間が8分に伸びていますが、Small input より入力値の制限が大きいので力技で解こうとすると試行数が爆発して間に合いません
    • 大会が終わってから正誤判定されるので回答データを送った時点では正解かどうかわかりません
    • こちらは1回しか挑戦できません

最終的に大会自体の制限時間(最近のQRは27時間、ラウンド1〜3は2時間30分など)が終わった時点で

  1. Large input の正誤判定をして、正解の場合はポイントが加算され
  2. 獲得ポイントが高い順にランキング
  3. 同点の場合は最後に正解データを送った時間が早い順
    • ただし正解した Small input に wrong try がある場合は wrong try 1回につき4分加算(ペナルティ)

という順位付けがされます。

GCJ2106-QR 振り返り

さてそんなGCJ、この週末にQR(Qualification Round;予選大会)が行われました。
このQRで30pt以上獲得すると予選通過となり、Round 1 に進出することができます。

今年のQRはわりとすんなり解ける問題ばかりだったので軽く問題を紹介します。
全部で4問出題されました。

※以下には若干のネタバレを含むので自力で挑戦してみたい方はご注意ください※

Problem A. Counting Sheep

羊を数えて眠りに落ちる話です←
(英語では sheepsleep の音が似てるからsheep sheep言ってるうちに眠くなるって話だけど
日本語で「羊が1匹、羊が2匹…」と言っても一向に寝付けないよね…)

入力値 N に対して 2×N、3×N、… を考えたとき、各桁の数字に 0〜9 までの10種類の数字が
少なくとも1回ずつ全種類出現したときの値はいくつ?という問題。
N=0 の場合は何倍しても 0 のままでほかの数字を見つけられないので眠ることはできません。
そこだけ気をつければ難しくない問題。

Problem B. Revenge of the Pancakes

パンケーキを全部表(happy side)を上にして提供したいウェイターのお話。

途中のパンケーキだけひっくり返すことはできなくて、上から任意枚一気にひっくり返すそうなのだけど、
最短何回ひっくり返すか以前にその非効率を改めるべきではないかと思ったりする不条理さが競技プログラミングの醍醐味です(?)

-++--+++++++ にする場合、最初の1枚をひっくり返して
+++--+ 次に最初の3枚をひっくり返して
-----+ 最初の5枚をひっくり返して
++++++ なので最短3回、みたいな。

どうすれば目的を達成できるか考えれば難しくありません。
Analysis ではひっくり返すことすらなく
表と裏の境界の数だけ求めて答えにしています。なるほど…

Problem C. Coin Jam

2進数で 1...1 と表現されるN桁の値が、2進数〜10進数のいずれで解釈した場合も素数にならないとき
その値を jamcoin と呼ぶ(っていうストーリー)。

N桁の jamcoin を J個見つけて、2進数〜10進数それぞれで「自明でない除数」(ようするに1とその値以外の約数、割り切れる数)を列挙する問題。
高速な素数判定モジュールがなくても自分で作ればなんとかなるレベルです。QRだし。
「全て列挙」でなく「J個見つける」だけなので、ある程度まで約数を調べて割り切れない場合は
「素数かもしれない数」扱いで回答から外しちゃってOKです。なので難しくないですねー。

私はJ個に絞らず(自分のプログラムで)見つけた jamcoin を全部出力して1回 wrong try 喰らいましたorz

Problem D. Fractiles

昔Fractal文明が作ったartworkが汚れていて元のパターンがわからないので、
大学院生にバイトさせてタイルを磨いてもらう。どのタイルを磨けばパターンが判別できるか?というお話。

アルゴリズム以前に頭のなかでどのタイルは何枚目の影響を受けているかを考えられるかが肝です。

def create(sequence, count):
    atwork = sequence
    for n in range(count - 1):
        atwork = ''.join((atwork if tile == 'L' else '-' * len(atwork)) for tile in sequence)
    return atwork

def test(K, C):
    print('K={} C={}'.format(K, C))
    for n in range(2 ** K):
        sequence = ('0' * K + bin(n)[2:])[-K:].replace('0', 'G').replace('1', 'L')
        print('{} => {}'.format(sequence, create(sequence, C)))
        print('')

test(3, 3)
test(3, 4)
test(3, 5)
test(3, 2)
test(4, 3)
test(5, 3)

こんな検証コード書いて表示させてみたりしてました。
1タイル調べれば(磨けば)オリジナルパターン Cヶ所の中にひとつでも G があるかどうか判定できるので
K÷C+1人の大学院生がいれば効率的にKヶ所の G の有無をチェックできます。

まとめ

以上、GCJの紹介とGCJ2016-QRの振り返りでした。
興味を持った方はぜひ!来年の GCJ2017 に挑戦してみてください!

参考になるかどうかわかりませんが、私のコードは
このあたり(Rank549 tama.eguchi)から
ダウンロードできます。

そういえば昔ジャムの海におぼれてたなぁ…もう4年も前かorz _

この記事を書いた人

tama