チームライブラリ

うちのチームのライブラリを公開しておきます
半分ネタなので、こんなのいつ使うんだーとかいうやつはバグってるかもしれないです

http://up.chokudai.net/src/chota1219.pdf.html
ぱすわーどはてきと

追記: 二円の共通部分面積バグってるので使っちゃダメです(誤差死する)

引退&これから参加する人へ

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


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


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


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


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


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


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


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

World Finals 2010

開始

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

1時間経過

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

2時間経過

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

3時間経過

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

4時間経過

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

終了

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

冬コンテスト

開始

簡単な問題がない!!!
JがただのDPな気がしたので提出したらWAったorz
間違いに気づいて直したら二乗のDPじゃなくて三乗になってしまった…のでパス
きたまさがAの最小二乗法やってようやく1AC

1時間経過

Cの漸化式をがんばって立てて2AC目
早くも解ける問題がなくなる…
みんなJいっぱい解いてたから実は1000^3/6くらい間に合うんじゃね、とか思って出したけどTLEorz

2時間経過

GCJで昔やった問題を思い出してBを通す
空間凸包をO(N^4)でてきとーに書いて通す
空間凸包は、同一平面上の点を列挙した上で平面凸包したけど、摂動させればよかったのか…
Jがいっぱい通ってるのでもう貪欲に違いない!と決めつけてかかるも通らないorz

3時間経過

Hをきたまさががんばって通す
いっぱい通っているJとSJTUが通したIをみんなで考えるも全然通る気配がないorz

4時間経過

しかたないので嘘DPでJを通すw
Gやり始めたら超簡単で20分くらいで通った…
Iにランダム投げてしゅーりょー

終了

7問解けてなんとか_(ryには勝てたけど、SJTU強すぎ…
自分がずっとJ考えてたのが明らかにまずかった
Standingとか参考にせずにとっとと幾何&探索やるべき

東京大会

優勝した!!!
これで2回目の世界大会がほぼ確定したっぽい
ついに後1試合のみとなってしまったわけで、ちょっと真面目に感想を書いてみる


チーム戦であるICPCで勝つためには、個人力も重要だとは思うけど、一番重要なのはやっぱりチーム力だと最近は特に思っていて、今回はちゃんと真面目に夏合宿後から毎週1セットずつ計5セットのチーム練習を行って臨んだ成果が発揮できたと思う

最近の流行はペアプロから並列プロ?に移ってきているようで、とにかくみんなコーダーで本当に難しい問題だけペアプロするらしい[要出典]
最近はそれをかなり意識して練習していて、印刷待ち軽減のため画面二分割とかも取り入れ、今回はほぼ常に新しい問題を解き続けることができた

たとえば、今回の序盤でいうと、
自分がCを組む→バグる→きたまさと交代→きたまさがDをやり自分は紙面デバッグ→きたまさがD解けたがバグ見つからないのでりゃんに投げて自分Hへ→りゃんがバグを見つけてC通る
みたいな感じでとにかくPCを止めることなく進めることができた

常に2問くらいが並列で進んでいるので、バグったときも詰まらないし、順位的には抜かれていてもかなり余裕があって、結果比較的簡単な8問目までを解き終えた段階で2位以下にかなりの差をつけることができた

その後も、
りゃんが8問目Hの連立方程式を解いている間に自分ときたまさで9問目の折り紙の解き方を相談し、H終了後すぐにEを始めれるようにし、三人でトリプロ→バグる→印刷して自分ときたまさで紙面デバッグしつつりゃんがVisualizerを組む
みたいな感じで折り紙を解き切ることができた

このペースで一人で解き続けるのは自分には絶対に無理だし、練習なしでこんな風に回せたとも思えないのでやっぱりチーム練習は必要だったと思う


さて、いよいよ次が最終戦
去年のような不甲斐ない結果にならないよう、今度こそは金メダルを取れるよう、がんばりたいと思う

台湾大会

奇跡の大逆転により優勝した!!!

0:00

Aがただのダイクストラだったので組んだらバグって時間かかったorz
きたまさがB意味不とかいうので飛ばしてCをやった
TLEしそうだったけど、まぁいけんじゃねと思ったら通った
他の問題聞いてもすぐに解法分からなかったので、読めないらしいBをやることにした

1:00

Bが簡単だったので通した
Fが通り始めていたのが、探索以外の方法が思い浮かばない…
探索を組んで最大サイズ試してみたら明らかにTLEorz
条件がついてたので実は最初に見つかった解でいいに違いないとか思って出したらWAったorz

2:00

Eも探索臭しかしなかったので、てきとーに探索したらTLEしたorz
Dもサイズ的に探索なのかなーと思って放置し、Hが最小二乗法+最小費用流らしいので組んどいてもらった、が、バグったorz
なんかトップにダブルスコアされて\(^o^)/ってなった

3:00

やけっぱちになって、Eでてきとーな仮説を立てて探索空間を減らしたら通ったwww
Hもバグが取れて通った
Iがいっぱい通ってたけど、まともな方針が思い浮かばなかったのでてきとーな仮説を立てて探索空間を減らしたらまたしても通ったwww

4:00

とりあえず嘘仮説立てるゲーということが分かったのでFもてきとーな仮説を(ryしたら通ったwww
Dもてきとーな仮説を(ryしようと思ったらまともなDPの解法が思い浮かんだのでまともに通した
最後10分ちょいでGを一気に組んだが通らなかったorz

終了

なんか\(^o^)/と思っていたのに結果8問解けて優勝してしまった!
終わった後にジャッジの解説があったがEもFも探索で解けるよとか言われてむりぽってなった



この調子で東京大会もがんばるぞーーー
ところで優勝した後の大会はオープン参加とかいうのは気のせいだよね…