今回のが２回目の世界大会だったので、もうこれで引退となります
自分は大学に入ってICPCに出会ったのがプログラミングコンテストに参加し始めたきっかけとなったこともあり、数あるコンテストの中でも一番気合を入れていました
今年こそは金メダルを取りたいと思っていましたが、最後の最後でミスをしてまたしてもメダルなしに終わってしまい、期待に応えられずとても申し訳なく思います
非常に悔しいので、敗因を分析して、これから参加する人たちの役に立てればと思います

まず、今年の自分たちの戦略について
うちのチームは自分ときたまさの二人コーダー体制で、それぞれ得意分野の問題を担当します
解法の分からない問題は、相談しあって考えます
解法が分かった問題は適切なコーダーに割り振ります(１問を解くにあたってもこの部分は任せた、みたいなことをします)
コーディングはこまめに交代しながら行い、ちょっとでも考えたくなった瞬間に交代します
この際に印刷では時間がかかるので画面を二分割します
ペアプロは実装の重い問題以外ではあまり行わず、デバッグは終盤以外基本的に紙面上で行います
とれないバグは終盤まで放置して次の問題に行きます

最近はチーム練習にロシアのSGUというジャッジを使っていて、この戦略でいい感じにいっていました
ロシアのセットなどでは、数学問題やアルゴリズムさえ分かれば組むのはそんなに大変じゃない問題(TopCoderで出そうな問題)が多く、いい感じに交代しながら問題を解くことができたのですが、今回の世界大会では実装の重い問題しかなく、きたまさの担当する問題がなくなってしまいました
というか、ロシアのセット以外、数学問題やアルゴリズム考える問題なんてあまり出ないので、探索・幾何・構文解析・シミュレーションといった実装ゲー練習をした方が良かった気もします

正直、このような問題セットの傾向の違いは非常に重要だと思います
例えば、OBOG会の合宿や、この間の冬コンテストなどでは自分たちや_(ryと、その他の国内チームの間にすごい差がつきました
一方、東京大会での成績にはほとんど差はつきませんでした
考える問題の少ないセットでは、確実にコーディングがボトルネックになります
今回も、特にはまっていたわけではないのに、気がついたら残り２時間とかになっていました
oxyさんとも話していたのですが、解法のアウトラインを考えることと、実際にコードにすることの間にはかなり開きがあり、組み始めてから、ここどうしたらいんだろう、とかいうことになることはよくあります
この部分を埋めて、実際にコーディングを始める前に、実装方法の詳細について考える練習をするといいのかもしれません
また、解法がわかっていても、チームメイトと楽な実装方法について議論するといいのかも

自分たちのチームは結構実装ゲーに強いイメージが持たれていたみたいですが、実装ゲーの練習するのはあまり好きではないので、コンテスト中に解けなかった実装ゲー問題とかをけっこう放置していましたが、これが良くなかったと思います
例えば、ロシアのチームは合宿で日本から持っていった空間幾何の最終防衛ライン問題を終了後にがんばって解いていました
こういったのの積み重ねで実装力がつくのではないでしょうか
日本のICPCの問題もOBOG会みたいに考える問題が多くなればいいのに、とかよく言っていましたが、もうICPCというコンテストはTopCoderやGCJとは別物であると割り切ってそれ用の練習をしないといけない気がします

コーディング量が多いセットではチームワークが非常に重要だと思います
今まで個人練習ばかりだったのを改め、今回はチーム練習をしっかり行うようにしました
１月は毎週末２セットの練習を行いましたが、それでもこれで十分だとは思えません(とはいえ、キャンパスが違うのでこれ以上練習するのは不可能で、どうしたらよいか分かりません)

というわけで、今なら次の戦略をとります
二人or三人コーダー体制
問題読んだら解法が分かっていようと相談して楽な解法を考える
画面分割して数分おきくらいで交代しまくりながら組む
ペアプロとか遅くなるのでいらない、むしろコーディングしてないときに解法の相談してバグってないかチェック

1問30分で解くのは大変でも、5分コーディング10分考えるを6セットやれば解けるに違いない！？
きっと_(ryならやってくれるに違いないと期待しておきます

2010-02-07

SRM 460

TopCoder

帰国してすぐで寝不足がやばかったけど欝なICPCの気晴らしのため参加

250

てきとーに探索した
頭が回らなくて色々バグったorz
218.76

500

DPするだけ
確率計算をミスってなんか足して1にならなかったけど係数考えるのもめんどかったのでてきとーに正規化した
443.95

1000

全域木or全域木+一本となるのを数えれば良い
全域木は行列木定理とか使えば簡単に計算できるけど、もう一本追加するのがよくわからかなった
追加してできて閉路上の辺数によって重複度が変わるし、どうやればいいのか謎

Challenge

結構落ちてたけど、見つけれなかった

合計662.71の4位
2886 → 2952
久しぶりにいっぱい上がった

2010-02-05

World Finals 2010

ICPC

開始

Aからやろうと思ったらいきなり構文解析だったのでパスして色々読み始める
Jが簡単そうだったので、どうせてきとーにやっても間に合うだろと思ってくんだら案外遅かった
座標圧縮するだけのCをきたまさが組み始める
Aをまじめに組みなおして提出→AC

1時間経過

座標圧縮が組めないらしいので交代して書き直してCを提出→AC
ただのDPのGを組んで提出→AC
実装ゲーばかりできたまさの解く問題がなくなる…

2時間経過

やるだけゲーらしいBをきたまさが解きつつ、Dを解く→一回WAの後AC
構文解析は得意なのでAをやることに決める→サンプルが通らない！
変数代入まで右から評価…

3時間経過

流石にいまから構文木作るのに書き換えるのはだるいので、計算量やばくなるけど気にせずてきとーに修正
その間にきたまさがBを通す
Aのサンプルがようやく通って提出→RE！！！
どうやら要素数１のベクトルとの足し算は例の逆向きの場合でも出来るみたいなので修正→WA！！！
きたまさがKを組み始める

4時間経過

流石に原因が分からないのでSubmitデバッグ開始
どうやら、パース後にまだ文字列が残っている＝構文がおかしい、ということが判明
しかし、一向にバグが取れない…
きたまさがKを組み終えたがこっちはサンプルが通らない…
そのまま時間切れ…

終了

今年は合宿など含めて一度もバグッたまま終了したことがなくて、まさか最後の最後で２問もバグって終わることになるとは思わなかったorz
Aは結局１行コピペ修正ミスがあって、おそらくそこ直せば通るはずorz
しかもなんかテレビ中継でここ１行バグってますねーｗと晒しあげられていたらしいorz
Kは凸じゃない場合を考慮していなかっただけで、終了後数分で気づいたのでもうちょい時間があれば通せたはずorz
これで引退とかとても心残りだけどまぁしょうがない
順位はイマイチだったけど、Aのあほなミスさえなければ７問はいけた気がするし、来年の人たちならきっと金メダルを取れるに違いないと期待することにしよう
あと、WFとか実装ゲーしかでないので、まともな問題で練習しても無意味で、WFで勝つためには実装ゲー祭りの練習をする必要があるんじゃないかなぁと思った
実装量がハンパなく多いので、パソコンの前で考える時間がなくなるよう、こまめに交代しつつ組み続けるのがいいのかなぁ
トップのチームとかどんな風にやってんだろ

2010-01-31

World Finals 2010

ICPC

明日から中国のハルビンに行ってきます
本番は日本時間で2月5日の10:30〜くらい
なんでも気温が-30℃とからしい！
寒いの苦手…

2010-01-27

空間凸包

Algorithm

以前O(n log n)の空間凸包を組もうとして挫折してずっと放置してたが、こないだの冬コンテストで出たのでそこそこ高速で楽な実装を考えてみた。
とりあえず、４点が同じ平面上に乗ってるのはないとして、
1. 点を徐々に追加していく
2. 凸包の各面が見えるか判定
3. 見える面を取り除き、見える面と見えない面の境界と追加する点を結ぶ面を新たに追加
っていうのをやるとO(n^2)になる。

見える面と見えない面の境界を探すのに、以前は面の隣接関係を保持してたけど、そうすると新たに追加したときに隣接関係修正するのとかが意外とめんどくさい。
よく考えたら、辺i->jをこの向きに含むような面は一つしかないので、O(n^2)でいいならてきとーに二次元配列に記憶しておけばよくて、面abcに対しては、辺ba,cb,acを含むような面を調べれば良い。
こんな感じで実装してみたらまともなコード長になったのでこれならICPCでも使えそう。

int[][] vs = new int[n][n]; //vs[i][j]=辺i->jをこの向きに含む三角形が、まだ調べてない:0、残った:-1、取り除かれた:1
List<int[]> crt = new ArrayList<int[]>();
crt.add(new int[]{0, 1, 2});
crt.add(new int[]{2, 1, 0});
for (int i = 3; i < n; i++) {
	List<int[]> next = new ArrayList<int[]>();
	for (int[] t : crt) {
		int v = ps[t[1]].sub(ps[t[0]]).det(ps[t[2]].sub(ps[t[0]])).dot(ps[i].sub(ps[t[0]])) < 0 ? -1 : 1;
		if (v < 0) next.add(t);
		for (int j = 0; j < 3; j++) {
			if (vs[t[(j + 1) % 3]][t[j]] == 0) {
				vs[t[j]][t[(j + 1) % 3]] = v;
			} else {
				if (vs[t[(j + 1) % 3]][t[j]] != v) {
					if (v > 0) next.add(new int[]{t[j], t[(j + 1) % 3], i});
					else next.add(new int[]{t[(j + 1) % 3], t[j], i});
				}
				vs[t[(j + 1) % 3]][t[j]] = 0;
			}
		}
	}
	crt = next;
}

ちなみに、見えるかどうかの判定を衝突グラフを作って行い、点の追加をランダム順にすると期待値的にO(n log n)になるらしい。
点pから面abcが見えて面dbaが見えない時、新たに面pabができ、面abcが取り除かれる。
この時、面dbaから見える点の集合は変化せず、面pabから見える点は面abcもしくは面dbaのどちらかから見えるのでこれらだけを調べれば良い。
(計算量の解析の部分ちゃんと理解してないので、ほんとにコレだけでいいのかは知らない)
実はO(n log n)のもがんばれば意外と短く出来るのかなー？？