Google Code Jamの予選に参加してみた

GCJ

Google Code Jamとは？



世界のGoogleが主催するプログラミングコンテストです。

詳しいことはわかりません。

友達のid:ororogくんに勧められて以前登録だけしていました。

ルール

GCJのルールは楽しいです。
予選は３問あって、特に難易度順に並んでいるようには感じなかったけど、
A, B, Cの３問。
問題文は例のごとく英語で、その他に入力と出力のフォーマットの説明と
サンプル入出力があります。

各問題には小さい入力、大きい入力があって、大きい方が計算時間がかかります。

提出方法が面白くて、
PKUなどのようにコードだけ提出して、あちら側で
コンパイル・実行されるのではなくて、
手元に入力ファイルをダウンロードして（この入力ファイルは当然各人異なります）、
手元で実行して、出力ファイルを作成します。
これをGCJ主催者側に提出するわけです。

ダウンロード開始から提出までには制限時間があって、
Smallが４分、Largeが8分です。
また、Smallは何回でも提出できますが、Largeは１回勝負です。


もう一つ面白いと思ったのが、SmallとLargeの難度の絶妙性。
Smallの方の入力だと、PKUでいうところのTLEになるような解き方（愚直解法）でも
結構通ってしまいます。

でも、愚直解法は間違いなくLargeで落とされます。

今回はAとBでそれをやらかしてしまって、どちらもLargeは８分以内に提出できませんでした。

Cは反省を踏まえてSmallのときから、計算量を考えてコーディングしたので提出できましたが、
合ってるかはまだわかりません。（Largeはコンテスト終了後に結果発表。TopCoderのシステムテストみたいなもの…？）

以下で、問題AのSnapper Chainを紹介。

Snapper Chain



Snapperと呼ばれる指パッチンでON/OFFを切り替えられるデバイスを、

鎖のようにN個つないで、K回の指パッチンの後に

N番目の出力につながれた電球が点灯しているかどうかを答える問題。

1番目のSnapperの入力には電源がつながっているので、常にON/OFFが切り替わる。
各Snapperは自身がONで且つ、入力に電力が来ているときに、電力を出力する。

愚直解法。(TLE)

#include<iostream>
#include<cstring>

using namespace std;

int main() {
    int T;
    cin >> T; 
    for (int t = 1; t <= T; ++t) {
	int N, K;
	cin >> N >> K;
	bool power[N], state[N];
	memset(power, false, sizeof(power));
	memset(state, false, sizeof(state));
	power[0] = true;
	for (int snap = 0; snap < K; ++snap) {
	    state[0] = !state[0];
	    for (int i = 1; i < N; ++i) {
		if (power[i]) state[i] = !state[i];
		power[i] = (power[i-1] && state[i-1]);
	    }
	}
	cout << "Case #" << t << ": " << (power[N-1]&&state[N-1]?"ON":"OFF") << endl;
    }
}

指パッチンの度に、各状態を更新する。
途中で特定のSnapperに対して特殊な操作がされるような問題だったら
多少は効果的かもしれないけど、この問題はいちいちシミュレートしてたらTLEになる。

TLE後に気づいた解法。

#include<iostream>

using namespace std;

int main() {
    int T;
    cin >> T; 
    for (int t = 1; t <= T; ++t) {
	int N, K;
	cin >> N >> K;
	int mask = (1<<N)-1;
	cout << "Case #" << t << ": " << ((mask & K) == mask?"ON":"OFF") << endl;
    }
}

SnapperのON/OFFは２進数のビットそのものだった。
ちょっと手を動かしてみればわかるのに、問題読んだら何も考えずにシミュレートするコードを書き始めてしまって本当にどうしようもない。
PKUで何を学んできたんだと嫌になった！

がんばる！

[追記]
ギリギリ通過ひやひや（´ｗ｀;）
ラウンド１がんばりたい