てきとーな日記

2010-02-12

[]チームライブラリ 21:03

うちのチームのライブラリを公開しておきます

半分ネタなので、こんなのいつ使うんだーとかいうやつはバグってるかもしれないです

http://up.chokudai.net/src/chota1219.pdf.html

ぱすわーどはてきと

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

2010-02-07

[]引退&これから参加する人へ 20:41

今回のが2回目の世界大会だったので、もうこれで引退となります

自分は大学に入ってICPCに出会ったのがプログラミングコンテストに参加し始めたきっかけとなったこともあり、数あるコンテストの中でも一番気合を入れていました

今年こそは金メダルを取りたいと思っていましたが、最後の最後でミスをしてまたしてもメダルなしに終わってしまい、期待に応えられずとても申し訳なく思います

非常に悔しいので、敗因を分析して、これから参加する人たちの役に立てればと思います


まず、今年の自分たちの戦略について

うちのチームは自分ときたまさの二人コーダー体制で、それぞれ得意分野の問題を担当します

解法の分からない問題は、相談しあって考えます

解法が分かった問題は適切なコーダーに割り振ります(1問を解くにあたってもこの部分は任せた、みたいなことをします)

コーディングはこまめに交代しながら行い、ちょっとでも考えたくなった瞬間に交代します

この際に印刷では時間がかかるので画面を二分割します

ペアプロは実装の重い問題以外ではあまり行わず、デバッグは終盤以外基本的に紙面上で行います

とれないバグは終盤まで放置して次の問題に行きます


最近はチーム練習にロシアのSGUというジャッジを使っていて、この戦略でいい感じにいっていました

ロシアのセットなどでは、数学問題やアルゴリズムさえ分かれば組むのはそんなに大変じゃない問題(TopCoderで出そうな問題)が多く、いい感じに交代しながら問題を解くことができたのですが、今回の世界大会では実装の重い問題しかなく、きたまさの担当する問題がなくなってしまいました

というか、ロシアのセット以外、数学問題やアルゴリズム考える問題なんてあまり出ないので、探索・幾何・構文解析・シミュレーションといった実装ゲー練習をした方が良かった気もします


正直、このような問題セットの傾向の違いは非常に重要だと思います

例えば、OBOG会の合宿や、この間の冬コンテストなどでは自分たちや_(ryと、その他の国内チームの間にすごい差がつきました

一方、東京大会での成績にはほとんど差はつきませんでした

考える問題の少ないセットでは、確実にコーディングがボトルネックになります

今回も、特にはまっていたわけではないのに、気がついたら残り2時間とかになっていました

oxyさんとも話していたのですが、解法のアウトラインを考えることと、実際にコードにすることの間にはかなり開きがあり、組み始めてから、ここどうしたらいんだろう、とかいうことになることはよくあります

この部分を埋めて、実際にコーディングを始める前に、実装方法の詳細について考える練習をするといいのかもしれません

また、解法がわかっていても、チームメイトと楽な実装方法について議論するといいのかも


自分たちのチームは結構実装ゲーに強いイメージが持たれていたみたいですが、実装ゲーの練習するのはあまり好きではないので、コンテスト中に解けなかった実装ゲー問題とかをけっこう放置していましたが、これが良くなかったと思います

例えば、ロシアのチームは合宿で日本から持っていった空間幾何の最終防衛ライン問題を終了後にがんばって解いていました

こういったのの積み重ねで実装力がつくのではないでしょうか

日本のICPCの問題もOBOG会みたいに考える問題が多くなればいいのに、とかよく言っていましたが、もうICPCというコンテストはTopCoderやGCJとは別物であると割り切ってそれ用の練習をしないといけない気がします


コーディング量が多いセットではチームワークが非常に重要だと思います

今まで個人練習ばかりだったのを改め、今回はチーム練習をしっかり行うようにしました

1月は毎週末2セットの練習を行いましたが、それでもこれで十分だとは思えません(とはいえ、キャンパスが違うのでこれ以上練習するのは不可能で、どうしたらよいか分かりません)


というわけで、今なら次の戦略をとります

二人or三人コーダー体制

問題読んだら解法が分かっていようと相談して楽な解法を考える

画面分割して数分おきくらいで交代しまくりながら組む

ペアプロとか遅くなるのでいらない、むしろコーディングしてないときに解法の相談してバグってないかチェック


1問30分で解くのは大変でも、5分コーディング10分考えるを6セットやれば解けるに違いない!?

きっと_(ryならやってくれるに違いないと期待しておきます

2010-02-05

[]World Finals 2010 02:13

開始

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で勝つためには実装ゲー祭りの練習をする必要があるんじゃないかなぁと思った

実装量がハンパなく多いので、パソコンの前で考える時間がなくなるよう、こまめに交代しつつ組み続けるのがいいのかなぁ

トップのチームとかどんな風にやってんだろ

oxyoxy 2010/02/06 09:35 お疲れ様でした。Kは後なんか4点同時に地面につく場合に、その凸包をとって、その中に重心が入るかをみないといけないので、それも罠だと思われます。

2010-01-31

[]World Finals 2010 22:31

明日から中国のハルビンに行ってきます

本番は日本時間で2月5日の10:30〜くらい

なんでも気温が-30℃とからしい!

寒いの苦手…

2010-01-24

[]冬コンテスト 22:18

開始

簡単な問題がない!!!

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とか参考にせずにとっとと幾何&探索やるべき