ICPC強化合宿(9/18〜21)

7月の初頭、私達はICPC国内予選に参加し一応5位という成績で通過したのであるが、
アジア予選日本会場の大会で中国人が毎度毎度一位を掻っ攫っていくのが
とある方々?にとってお気に召さない様子で、
日本強豪チームを世界強豪レベルにまで持っていくことを目的として、
この度強化合宿なるものが画策されていたようである。


日本強豪チーム…とはあまりにも抽象的な定義であるが、
ここでは今回の国内予選で4問以上解いたチーム…とのことらしい。
ゆえに我らも召集される段と相成ったわけで、
新幹線でちょっくらそこまで、と東京行き。
本当はバスで来いとか無茶なことを言われたのだが、
虚弱体質な私は無論新幹線を選ぶのであった。
というか、会津大学と、うち以外はみんな関東圏なので、
なんというかもう、……。


…とまぁ、そんなことはどうでも良くて。
強化合宿では3日で19問の問題を本番形式で練習した。
Gokuri-Squeezeがやはりというか、強力無比だった。
19問中解けてなかったの2つだけだったのかな。
うちらはというと…
なんかもう、あほな部分だけを見せ付けたような印象であった。
今回の練習、入力がいやらしすぎ…だと思った。
解いても解いてもAcceptしない。
私はこんなところに"世界を統べる冷ややかな悪意"(cf.暗黒館)を感じ取って、
のっけからもう自暴自棄になってしまった。
実際問題、入力はコーチの人たちが用意したもんだったし、
しかもrejectされるのをみてケラケラ笑っているではないか!


そこから我らの反撃が始まったのである。(…うそ)
発端はこの問題。

1<=x,y<=9,(x,y)を中心とする半径1の円がいくつか有る。
それらにカバーされる部分の面積を求めよ。
(誤差は最大0.01に抑えよ)

これは実は幾何的に解くのは非常に難しい。
これまた他の問題が全然Acceptしない状況に痺れを
切らしまくっているときであった。
この問題は精度があまり要求されない、かつ座標の範囲が狭いので、
メッシュに切ったりするのが、まぁ普通な解法であろう。
が、そのように解くぐらいならもっと簡潔な方法がある。
モンテカルロ法である。誰しもが一度は円の面積を求めたことが
あるはずである。そして、そのあまりの精度の悪さにため息を漏らしつつ
それ以降まず使わないモンテカルロ法
私も円の面積を求めたときに、うわっ、一億回もやったのに
x桁ぐらいしかあってへんで。とか思ったような記憶がある。
(何桁ぐらいあってたかは忘れた)
まぁ、どっちにしろ3桁ぐらいはいけてたと思うので
ちゃかちゃか〜と試行回数100万回、1000万回、1億回、
の3バージョンをSubmit。他の問題で大真面目に
rejectを喰らいまくっていたので抵抗感はかなり少なかった。


そんなこんなで、うちのチームはすっかりモンテカルロチームとして
認識されることになってしまった。
その後の問題でもかなり投げやりプログラムで通しちゃったのもあり、
最後の講評で、SubmitしまくってAccept数を
稼ぐやり方は最近はあまりお勧めしない…とか言われてしまった。
はぁああ…私はそんな戦略をとったことは一度もないのにな…
というか、本番でrejectされたことは生まれてこの方一度も無い!
とかなんとか言ってみても仕方がないなぁ。はぁ。


で、合宿の成果としては…
Gokuri-Sqeezeの圧倒的な強さも分かったし、
うちのチームの駄目なところもよく分かった。
(安定結婚のアルゴリズムとかウォーシャル・フロイド法ぐらいは、
名前だけじゃなくて、ちゃんと中身も勉強しとこうな!)
結局総合順位は7チーム中4位ということで可も無く不可もなく。
…これからもっと勉強します…。