UTPC2009

今年も参加しました。
http://www.utpc.jp/2009/

結果は7問で6位という残念なものでしたが、
面白い問題がいろいろあって楽しかったです。
一つの問題にはまって他の問題が全然考えられなかったのが悔やまれます。

当日の様子を書いておきます。

A

問題がなかなか開かず焦る。
とりあえず普通に簡単な問題だったので通す。

B

DP書いて通す。
12問中の2問目にしてはめんどい。

C

2人の人が9枚ずつ与えられたカードを一枚ずつ出して云々という問題。
はまった。
1ターンずつ適当にカードを出し合ってビットDPすれば
(2^9)^2*9^2ぐらいで終わるんで、それで組んだら手元で0.5秒ぐらいかかるプログラムができた。
サブミットするとTLE。どうしたもんかなあと。

E

そうこうしているうちに早くもEが解かれてしまったので、Eに変更。
ぱっと見分からなかったけど、こんなに早く解かれるなら簡単に違いないという推理から、
これはどうやっても同じなのではないかと予想。
足し算したときの数の総和は変わらないか10減るか。
なので、最後に残る一桁の数は常に同じ。
10減る回数も決まっているので、結局どうやっても足し算できる回数は同じ。
適当に書いて適当に通す。

D

Dが解かれたので、Dに進む。
完全に後手後手になってきてて、もう今日は駄目かなあと思い始める。
呼んでみると実装するだけで仕様も単純だったので
さっくり通す。

G

今度はGが解かれたのでGに進む。
よく分からなかったけど、TLEにならない程度回してWAもらったら後で考える、
ぐらいで実装を始める。
普通にAccept。
あとで考えてみたが、ループするケースは二者間往復しかなさそうなので、
これは正しかった。

C

ほかに解かれてる問題がなかったので、Cに戻ってくる。
もう一回一から考え直したら、これは片方出す順固定して
もう片方の出す順番を全部試すだけじゃないかとやっとのことで気づく。
こんなことに気付かなかったなんて、悔しくて仕方がなかった。
でも、一回解法を思いついてしまうと、それに思考が縛られてしまうのは
仕方がないのかもしれないと思った。
そうして、ようやくAccept。

F

とりあえず残り全部読むかと思って、読む。
Fがよさそうな感じがしたので、実装開始。
サイズが50000なのが心配だったが、O(nm)のアルゴリズムで、
bitsetでやれば間に合うんじゃないかと思った。
完成したプログラムはワーストケースで手元で0.7秒ぐらいだった。
Cのこともあったので、どうかなと思って出したが、
結果はTLEであった。

I

二時間ぐらいFの高速化をやってて、さすがにまずいんじゃないかと思ったので、
スコアを見てみるとIがそこそこ解かれてるっぽかったので、解くことにした。
猫が自力で行けるときは0。
そうでないときは人が最小限の扉を開けてやらなければならない。
人が最初にいる場所と、猫が動ける範囲と、ゴールに猫が自力でたどり着ける範囲の三つを
結ぶ最小ルートがどうなるのかなあと考えていたら、最適な時はY字になるはずと気付いて、
それが分かれば後はすぐであった。
と思ったが、自力で行けるケースを書くのを忘れていて1回WAを食らった。
直してサブミットしようとしたらコードを二重に張ってCEをもらった。
三度目の正直でAC。

F

残り時間1時間ぐらいで、Fをやるかほかにあと1問別のやつを解くかで、
結局Fに戻ってきた。
Hはサイズが大きすぎて厳しそうだったのでパス。
Jは幾何よく分からないのでパス。
Kは式をちょっと書いてみたら泥沼になったのでパス。
Lはなんかうまい方法があると思って少し考えたけど全然わからなかったのでパス。

一時オブジェクトを作らないようにしたり、
bitsetをやめてsetにして枝刈りを入れてみたり、
setをunordered_setに変えてみたりいろいろやったがダメ。
unordered_setに変えたときは結構テストケースが進んでいるような手ごたえがあったが
結局は通らず。
状態数が爆発するケースがあることが分かったので、それを突っ込んでみたら
setでは全然終わらず。
諦めてbitsetを高速化するが、手元で0.4秒ぐらいまでになったものの
相変わらずTLE。
もうだめだ、というところで終了。

終了後

twitterでF後ろからやったら一瞬と聞いて相当ショックを受ける。
なんで気付かなかったんだ。
ちょっとこれはしばらく立ち直れないかもしれない。
よくよくも考えると、こんなにたくさんの人が
こんなに激しいチューニングをして通しているわけがないじゃないか…。

勝負としてはC手間取った時点でスコアでは勝てなくなってたので、
もうこれは駄目だった。仕方がない。

参加しての感想としては、
参加者の層が、ちょっと前では考えられないほど
厚くなってきてるなあと思った。
7問以上正解者が16人もいるのがそれを示している。
現役が強いなあという印象も受けた。
今年の世界大会は期待していいかな。

最後に主催者の皆様、このような楽しげなイベントをありがとうございました。
また来年があればよろしくお願いします。