読者です 読者をやめる 読者になる 読者になる

UTPC 2013

競プロ

なんか、3位でした。(+5点)
良問がたくさんあって楽しかったので書こう。

*11時に目が覚めて11:25に起きる(この時点で結構ぎりぎり)
*12:44頃につけそうな電車に乗った(この時点でかなりぎりぎり)
*電車遅延(この時点でちょい遅刻)
*乗り換えが必要だったことに気づかず東京駅まで行く(この時点で完全にアウト)
*コンテスト開始(@山手線)
*FAが欲しかったので、競争率の低そうな200点問題を漁る。

・Eは構文解析っぽい問題文で、なんか大変そうな印象を受けたのでそっと閉じた
・D~Gあたりをざっと見てFを解くことにする。
・制約あんまり読んでなかったけど、N log Nとかは無理そうな気がした。
・N<=1000というのを見つけて毎回MSTやらせてもらえそうという感じになる。
*不要な辺に関する考察と計算量解析をして実装し始める。
*渋谷に降りてからも少し実装してAC

・他にもFを狙ってたが居たらしい
・FAであることを確認し、GとHを考えながらヒカリエに向かう
・Gは部分点の自明にぶたん貪欲を拡張するんだろうなぁというところまで考えたけど詳細まではあんまり詰めなかった。
*Hは一瞬で牛ゲーだと分かったのでエレベーターの中で実装
・会場に着き、chokudaiさんの前が少し空いていたので座る
・制約を見て「あっなんか工夫いるのかな」と思ったけど通った。FA
・打ち切りとかしないベルマンフォード書いたけど1秒以内だった。グラフを隣接リストじゃなくて辺の集合で持ってたから早かったのかなぁ。闇
*Gもちょっと詰めて解いたけど、takayutaプロにFAを取られた。
*いったん解くものが無くなったのでAからやり始める。

・まぁA、AC
・Bで1WA・・・
・Cはサンプルにあったコーナーケースで1WA(ダメ)
*D難しい。貪欲を書いたけどWAだったので考察する。(256までしか試してなかったのがWAの原因っぽい)
・それぞれの頂点について「少なくともX以下」みたいな条件を計算してソートして順番に当てはめる、という手法が正しそうなことをなんとなく証明したので書く。WA
・512まで試すようにしたら通った。
*この時点で1位で、2FAを取っていたのでちょっと嬉しくなる。
・BとかDに神経を使ったので結構疲労していた。
・EIJKLが残っていた。
・E:2SAT=グラフというイメージが強くて、グラフ上でウンウン悩んでたけど解けない・・・
・I:なんとなく解けそうな気がしたが、実装が重そう・・・(この手の問題ではよくある話?)(解けそうというだけで解けてはいなかった)
・J:ランダムであることを使うんだろう程度しか分からない。
・K:wataさんのやばいフロー問題かーと思ってあまり考えず10^5に絶望して閉じた。(そのせいで問題をちゃんと読めてなかった)
・Kは「入力はグラフではなくフローが与えられる」というのを読めていればまだ人間に解けそうな問題に見える。解説の本質の部分あまりよく分かってなかったからまた今度考えよう。
・L:めっちゃ簡単に見えて全然そんなことないことに気づく。部分点は取れそう。
*IをtakayutaプロがFAしていたのを見て、さすが若手超有望JOIerだなぁと感心する。
・僕みたいな老人にはそんな元気無いよぅとか思いながら休憩していた。
・問題を考えながらchokudaiさんやtozangezanの顔をぼーっと眺めた。目が回復した。
・中学生にはまだ負けたくないなぁという意地でちょっと元気を取り戻す。
・解けそうなのがIしかないなぁと思いながらIをできるだけ実装が楽になりそうな方向で考える。
*IはなんかHeavy-Lightっぽい臭いがいたのでそういう感じで考える。(Heavy-LightデコンポではなくHeavy-Light)
 たくさん分岐がある時は
 ・部分木を全部setに加える
 ・各部分木に潜る時にはその部分木をsetから取り除く
 ・そんで戻ってきた時にまたその部分木をsetに加える
 みたいなことをすれば良さそう。
 だけど、細長いケースでdel,addをしまくるとO(N^2 log N)とかになるのでやばい。
 一番でかい部分木に対してはdel,addをしなくて済むように出来れば、よくある計算量解析によりO(N log^2 N)ぽい
 一番でかい部分木に最初に潜ることにすればそう出来る。解けた。
・残り時間が少なかったけどこの方針map先生のおかげで実装軽いので実装も割とすぐできた。
*mapとか使ってたのでTLEがちょっと怖かったけど、通って歓喜。(余計な処理を書いてて計算量悪くなってて1回TLEを出した)

・おなかへったclarをなげたらyさんがモーニングサンダーを持ってきて下さった。うまうま。
*まぁ残り時間もあまり無かったので無難にLの50点取りにいく。
*終了、3位やったー

・スピリチュアルさんにEの解法を聞きにいく。めっちゃなるほどだった。
・解説が始まるまでの間にきたゆたに膝枕してもらったけど、ズボンの生地のせいか、固すぎて気持ちよくなかった。
*Lの解説に感動。

情弱だったので懇親会は申し込んでおらず、とざんとサイゼゲーセンして帰った。

〜各問感想まとめ〜
A:A問題として良い感じでした。問題文中に穴i個の文字列が書いてあったのがありがたかった。
B:つらい・・・
C:2つのグラフは全く同型であるということにしても解法は変わらなさそうでかつ実装等が楽?普通に良問
D:貪欲が非自明で難しかった。個人的に解いた中で一番苦戦しました。
E:なんというか、勝手に作っていた固定概念を覆してくれた良問。
F:MSTの仕組みが多少分かってないと解けない良問。
G:Fullで使えるという要素が入っても貪欲で解けるんだなぁ。うまく出来てるなぁと思いました。
H:牛牛牛牛牛
I:見たこと無いタイプの木+データ構造の問題で面白かったです。
J:あまり考えず、解説を聞いてなるほどと思う感じの問題。ユニークで面白い:)
K:問題ちゃんと読んでたら解けうる問題だったなぁ。実際に解けるどうかは別として、少し悔しい。
L:解説はキツネにつままれた気分でした。うますぎる・・・

ソースコード
A B C D F G H I

追記:deleteのかわりに両側から挟む感じでやればO(N log N)じゃん・・・短いI

〜まとめ〜
制約があれだったというのは残念ですが、問題はかなり面白かったです。
(ジャンルがグラフに偏ってるのは出題陣のクラスタから自明なのでしかたがない?僕としてはwelcomeでした。)