UTPC参加記録

ICPC

今週末はUTPCというのに出てました。
http://www.utpc.jp/mjudge/standings.cgi?cid=0
なんというか、私は若い世代の人と戦ったことがないような気がするので、
良い機会なので参加してみました。
結果はみごとに屠られましたとさ。
なかなか勝負勘はもどらんのう。


しかしなんというか、こういう戦うプログラミングというのは良いですねえ。
もえますねえ。
途中熱くなりすぎて意識が飛びかけました。
もっとこういう機会があると楽しいのですけど、なかなかそうもいきませんねえ。
SRMに出るというのもいいんですが、あれは時間が短すぎて
終わった後に不完全燃焼感しか残らないですねえ。
あと英語なので、英語をはやく読める人には勝てる気がせんです…。


今回久しぶりに出てみて、いろいろ勉強になりました。
二年前当時に比べて、自分自身の変化というか、
ずいぶん優柔不断になったような気がします。
この問題解けそうだけど、本当に解いて大丈夫なのかなあ、
すっぱり解けるかなあ、とか、しばらく考え込んでしまうようになっていたり。
自分がどれぐらいのスピードでどんな問題を書けるのかというのが、
正確に把握できなくなってるのですかね。
昔はそんなことは無かったのに。
あと、自分よりも初速が速かったりする人がたくさんいてびっくりしました。


問題ですけど、A-Gは特に言うことはないです。
あ、やっぱり言うことはありました。
Aで誤審があってWAを喰らってびっくりしたというのと、
他の人たちがなんでFの誤答が多かったのかが気になります。


Hは前にどこかで解法を聞いた覚えがあったような気がしたのですが、
忘れていたので今回はスルー。
あとでoxyさんに聞いて、行列の乗算でOKということになりました。
Iはどうみても状態数が少ないので適当にやればOK。
ゴール状態から幅優先とかで良かったのかもしれませんが、
面倒なので、ターン数つけてDAGにして無理やり解きました。
ターン数を確証のある範囲まで余裕もたせてたらTLE喰らったので、
確証はないが少なくしたらとりあえず通りました。
Jは何気にICPC関係では初めて書いた演算子優先構文解析。
Kはなんで通らなかったのかなあ。
手元の考察で4以下ですべてのケースがOKになる、と出てきたので、
0,1,2,3のケースを列挙して送ったのですが、
漏れがあったか、実装がバグっていたか。
0,1,2のケースは間違いようがないと思うので、3のケースかなあ。
Lは面倒そうだったので時間内には手をつけませんでした。
二つのプレート間を移動できるかどうかのグラフを作って、
あとは最短パスを見つけるだけだと思うので、
昨日書いて送りましたがTLEでした。
移動できるかの判定をO((h*w)^3)でやっているので、
手元でも一番重いケースで10秒とかかかります。
通るわけねえ。
O((h*w)^2)で間に合わせる方法も考えたのですが、
実装がめんどくさそうなので、もう諦め。
諦めが肝心ですよ。そして、貴重な週末が消滅。


先達に習ってソースを晒す。
http://fxp.infoseek.ne.jp/tmp/utpc.tar.bz2
Lが長くなりすぎた…。