アメリカのプログラミングコンぺ、TopCoderに参戦してみました。TopCoder内ではいくつかの競技があるようですが、僕が参加したのはAlgorithmという制限時間内に問題を解き早さを競うというものです。三問出題され、それぞれ早く解けば解くほど高い点数がもらえ、参加者全員に点数に応じたレートがつけられます。使用できる言語はJava、C++、C#、VBですが、基本的にプログラムの速さは得点に関係ありません(でも1入力に2秒以上かかるものは遅すぎるのでアウト)。とにかく早く提出するのが全てなので、得意なもので書けばいいと思います。僕はJavaです。全然得意じゃないですけど。

まず、参加者は大きく二組にわけられます。それまでのレートが1200以上の人はDiv1、それ以下や初参加の人はDiv2。僕は初参加なのでDiv2です。当然こちらのほうが問題もやさしい。レートはDivisionの中の相対評価でつけられるようです。

それぞれのDivisionで、さらに20名ずつのグループにわけられます。競技はこのグループの中で行われることになります。問題は三問(それぞれ250点、500点、1000点)。最初の75分でこれらを全て解きます。休憩をはさみ、15分間でグループ内の他人のコードを見てその間違いを探します(他人のミスを見つけるとポイントがもらえます)。ここで競技は終了となり、各解答に対してシステムのチェックが入ります。これに無事パスすると正式にポイントが与えられ、レートがつけられます。

250ポイント問題
文字列を検索する系。 5分くらい。230ポイント獲得。

500ポイント問題
二円の交点の数を求める系。 8分くらい。410ポイント獲得。

1000ポイント問題
ワードパズルみたいなもの。 一時間以上考えた。例示された入力に対しては正しい答えが返せるが、メソッド内で再帰していたためワーストケースどころかちょっと長い入力に対してはタイムアウト。とりあえずぎりぎりにダメもとで提出してみた。420ポイント獲得。

The Challenge Phase
他人のバグ探しをする時間。ここが一番楽しかった。バグをみつけたらそれを誘発するようなテストケースを作成して送り込んでやる。うまく行けば+50ポイントで相手のポイントは帳消しになるが、失敗すると-25ポイント。この撃墜も早いもの勝ちだ。とりあえず1000点問題については自分の解答がタイムアウトすることがわかっていたので似たようなものがないか探す。再帰してるヤツがいた！しかしその解答に対してタイムアウトする入力を作っている間に他の人に撃墜されてしまった。メインの画面に戻ったら、僕の1000点問題も撃墜されていてワロス。-420ポイント。最終的に一つバグを見付けて撃墜。50ポイント獲得。解答者は日本人の方でした。でも戦場だから！

The System-Testing Phase
競技が終った時点で690ポイントくらいだったのだが、システムチェックで500点問題が落ちた…。500点問題は作っている途中に穴に気づいたのでそれを埋めて、Challenge Phaseでも二人の攻撃を弾いていたので大丈夫だと思っていたが甘かった。-410ポイントで最終的な結果が280ポイントと大変残念なことになってしまいましたが、それでもなんとかDiv1にいけるくらいのレートがつきました。250ポイント以下は団子になるので、それをわずかに超えていたことが幸いしたのでしょう。しばらくDiv1に居られるように頑張りたいと思います。

The Java Programming Language, Fourth Editionをちびちび読んでいる。さっきChapter6 Enumeration Typesを読み終えた。enumの各要素にはメソッドが定義できるので、Stateパターンぽいことができる。

Time.java

public enum Time {
	MORNING {
		public void greet() {
			System.out.println("おはよう");
		}
		public Time next() {
			return DAYTIME;
		}
	},
	DAYTIME {
		public void greet() {
			System.out.println("こんにちは");
		}
		public Time next() {
			return NIGHT;
		}
	},
	NIGHT {
		public void greet() {
			System.out.println("こんばんは");
		}
		public Time next() {
			return MORNING;
		}
	};
	public abstract void greet();
	public abstract Time next();
}

Test.java

public class Test {
	public static void main(String[] args) {
		Time t = Time.MORNING;
		t.greet();
		t = t.next();
		t.greet();
		t = t.next();
		t.greet();
		t = t.next();
		t.greet();
	}
}

コンストラクタも使うとこんな感じになる。greet()は各enum要素内でオーバーライドすることもできるようだ。

Time.java

public enum Time {
	MORNING("おはよう") {
		public Time next(){
			return DAYTIME;
		}
	},
	DAYTIME("こんにちは") {
		public Time next(){
			return NIGHT;
		}
	},
	NIGHT("こんばんは") {
		public Time next(){
			return MORNING;
		}
	};
	String message;
	private Time(String message) {
		this.message = message;
	}
	public void greet() {
		System.out.println(message);
	}
	public abstract Time next();
}

学校の課題プログラムくらいならこれで十分だろう。Stateパターンを使えってところでこっちを使った場合、どういうことになるかは知らないが。

そういえば先日元バイト先の人と飲む機会があったのだが、情報系の専門学校の子が「javaをフローチャートで習ってる」と言っていた。僕はまず自分の耳とそして彼女の言葉を疑い、それってシーケンス図のことじゃないの、と何度も確認したがどうやら本当にフローチャートらしい。フローチャートって情報処理試験以外でも使われてるんだ、と少し感動した。

The Java Programming Language, Fourth Editionを読んでいる。

・スタティックメソッドを使ってインスタンスをいじるのは、ゴールデンゲートパークでジョギングしてるやつがぶらさげてるウォークマンのシリアルを変えてくれとウォークマンの工場に言うようなもんだ。

• どんなものにfinal修飾子をつけるべきか
• • ・値が不変である
  • ・値がオブジェクト（インスタンス）が作られるときに決定されている
  • ・オブジェクト（インスタンス）を生成する際に、その値を求めるのが現実的かつ適切である

この三つ目、フィールドの初期化にコストがかかって、しかもそれがごくまれにしか参照されないときは、その値が必要になってはじめて計算するほうがコストが安い。これを遅延初期化(lazy initialization)と言う、なんてさらっと書いてる。まー当たり前といえば当たり前のことなんだけど。僕がはじめて遅延という概念に出会ったときは結構衝撃を受けた。

やはりいろいろ得るものがありそうだ。