UTPCに参戦しました
UTPC(東大プログラミングコンテスト)に参加しました．
東大の人とかしか参加できないのかと思って参加を見送っていたんですが，そんなことはなかったんですね．
大学コンテストという性格のせいか参加者はハンドルではなく本名を名乗ることになっていて，誰が誰なのかほとんどわかりませんでしたがとてもストイックで楽しめました．
結果ですが全体で9位だったみたいです．本名プレイなんで実はあんまり貼りたくないんですが全体のStandingsはこちら．
以下，問題ごとの何か．
開始
あんまり飯食ってなくて割とお腹すいてる．
12:00になった．A読む．足すだけ?
A Accepted(00:02)
Bを読む．宝くじの合計金額を知りたいらしい．
親切なことに，1枚の宝くじが複数の賞金にヒットすることはないそうな．ナイーブに文字列判定してやればよさそう．
B Accepted(00:07)
Cを読む．ぷよぷよのシミュレートらしい．「コンパイル」というタイトルが地味に笑いを誘う．
面倒だけどまぁDFSで連結成分の個数取って，DFSで連結成分の消去とかやればできる．
おじゃまぷよの扱いもまぁできるだろう．
少しバグりながらもAC．
中学生のときとか1日かけてぷよぷよのアルゴリズム書いた記憶があるけど，今だと一瞬だなぁ…．
C Accepted(00:22)
Dを読む．グラフっぽい．Warshall-Floydとかすればいいんでない?
文字列の入力に少し苦戦する．
あと，配列の要素の確保が少し不足していてRuntimeErrorを出してしまう．
D Accepted(00:40) (1WA)
Eを読む．ラノベ臭がする．
N*Nのマスにおいて，列と行に数字が書かれていて，その数字だけ列/行に印を入れたい．印の入れ方が一意的か否か判定せよ．
うーん，一意になることってそんなにない気がする．
まず，理詰めで一通りに決まるときは解はかならず一つしかない．当たり前．
逆も成り立つんじゃ?
…あまりちゃんと証明していないけど，理詰めで決められない場合は多分↓みたいな盤面があるはずなので，変換をすると二通りの解ができてしまう．本当かよ．まぁいいや送ってみよう．
書いた．投げた．当たりだったらしい．
E Accepted(01:00)
Fを読む．いかにもDPっぽい問題．
何通りあるか求めるのがUTFのバイト数によって違うのが面倒だけど，実装を工夫すれば割とさっくりできる．
書いた．
F Accepted(01:23)
さて，ここから泥沼にはまっていく…
Gを読む．現在の日付時刻と天体のデータが与えられるので，現在観測可能な天体をすべて列挙せよ，という問題．立体幾何．
問題文の座標の意味がよく分からない．面倒くさそう．Standings見てみるとiwiさんがHを解いてる．後に回してHやろう．(これがよくなかった．)
Hを読む．猫にえさを与える問題．nyaさんが作った問題のように見える．(が，違ったようです)
とりあえずy座標の情報はいらない．えさを与える点が決まったら隣り合う2点間に垂直2等分線を引くことで，猫の集まる領域を決定できる．
見た感じDPっぽい．
うーん，でもどうすればいいんだろう… 20分くらい考える．D[n]:=n番目のえさ入れを使うときに，とすればいいんでない? できそう．書く．
詰まる．n番目のえさに寄ってくる猫の数を数えようと思ったら，その両隣のえさ入れの座標が分かってないといけないんだよなぁ… 3変数．どうすりゃいいの．
もしかして2分探索? 最大のえさ数が分かればいいわけだし，それが求まったら左からGreedyに置いていけばいいんじゃ? (間違っている)
もう考え始めて40分くらい経ってる．僕の場合こういう問題が解けなくて本当に嫌になる．
Standings見る．I解いてる人が結構いる．分からないしIをやろう．
Iを読んだ．最短経路だけど，歩く道筋に禁手が決められていて，その通りには歩けないらしい．
ナイーブに10歩前のログを取ると50*50*4^10で死ぬよなぁ… 必要なところ(つまり禁手の接頭辞になっている部分)だけログを取るようにすると良いのでは．
最悪の計算量は分からないけどそこまで多くならないんでない? 書く．
制限時間もそこまで長くないのでとにかく速度重視で書く．ログはstringとかでやるよりはintのビットで管理するのがよさそう．(2ビットを1手に割り当てる)
色々バグりまくったが何とか完成する．1時間くらいかかった．なんてこった．
サンプル結構きつそうだし合うんじゃない? 投げる．WA．うおー…
どうしよう．
コードを見たりテストしたりするがよく分からない．うーむ，困った．8問は通したいなぁ…
もしかしたら現在の状態をlong longに割り当てているのが間違っている? 数値を少し大きくする．投げる．WA．まぁそりゃだめだろう．
刻々と時間が過ぎていって焦りが募っていく．
よく見たらこれはじく場合の判定間違ってないか．修正．投げる．WA．
まだ間違えていた．(というかサンプルが通ってなかった)．修正．投げる．1.98secでAC
1.98secって…危なすぎるだろこれ．(制限時間は2.00sec) まぁいいや．一安心．
I Accepted(03:55) (3WA)
さて，残りはGかH．正直どっちもよく分からない．
誰も解いていないJとかも読んでみる．体Zpの多項式の解の個数? よく分かんないなぁ…．2分ほど考えて辞める．
Hをもうちょっと突き詰めればなんとかなるんじゃないかと思って少し考えるが，自分はDP力が足りないのでHを捨ててGを取るのが良さそうだと判断してGをやることに．
書く．3次元幾何とかわかんないよ… もうわからなさすぎてDo it!! Do it!! とか聴いちゃってる．
Spaghetti Sourceに載っていたvalarrayとかを写すが，なんなんだこれ．よく分からないものは使いたくない主義の人間なので，だんだん嫌になってくる．
北極星の軸に合わせての回転とかどうすんの… もう嫌．Gを諦める．
残り20分くらい．Hを見る．2分探索，ここ直したらできないかなぁ．直した．サンプルが通る．おお?
なんでそれでいいのかよく分からない．…というかGreedyではないような気がする．もういい，投げる．WA．ですよねー．
残り10分．何もできない．終了．うーむ，なんか腑に落ちない．
感想
最初の6問は勢いよく解けたのですが，そこから先で一気に失速してしまった．
順位落ちまくってるだろうなと思ったのですがそこまで落ちてませんでした．
時間いっぱいあったのだしGとHのどっちか1つくらいは解きたかった．
問題セットですが，やはり面白い問題が多かったと思います．
Gは北極星の軸を回転させれば2次元幾何の範囲で解けたらしいです．素晴らしい．知らないことはできるだけ自分の知っている範囲に落とし込まないと駄目ですね．
幾何は去年の模擬国内予選と国内予選の問題を解けたので大体大丈夫だろうと思っていたのですが，まだまだ詰めが甘かった．難しい．
HみたいなDPは苦手なのですが，できる人は本当にすぐにできちゃうんだろうなぁと思います．うらやましい．
こういうのは練習してもできるようになる気があまりしないのでずっと放置してるのだけど，たくさん解いたらできるようになったりするのかなぁ．
