天下一プログラマーコンテスト2016本戦 参加記
予選Bの本戦出場権持ちの予選A通過勢を除いた繰り上げの繰り上げの繰り上げで本戦に出場しました。
実質最下位。
予選A
ABCやるだけD発想EつらいでABC3完
予選B
AやるだけBはDPやるだけ
Cで確率DPが苦手なのにバグらず一発で通ってしまう
DEが死
でもABC早解きと繰り上げで本戦出場
本戦
なんかエナジードリンク(カフェイン含む)が無限供給される。闇
カフェイン含有量だけ書いてなかったんだけどレッドブルとかと同じと考えていいんですかね……？
A/B
講義で巡回セールスマン問題をやっていたのでTSP来いと思っていたのですが4彩色問題。
なんかとりあえず辺がいっぱいあれば強そうなのでAはランダム配置に張れるだけ辺を張ったやつを適当に組んだ
Bは特に考えずにrandom_shuffleした(参考 : http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2550)
D
Cは文字列が苦手なので後回し
Dは制約からして2Nの形をしてるんだなぁと思う
予選AのCと似てる気がするので、どっちの部屋から始めて、どの作業をどっちでやるのかだけ決めちゃえばシミュレーションできるなぁと思って書く
なんか部屋の交代とか新しくできるようになったタスクの探索に変に計算量つかったからか数秒だった
C
すごい文字列
Aho-Corasickなら結構行けるのでは？と思ってスパソを見よう見まねで写す
が、スパソのAho-Corasickはfailした際にacceptを回収していないらしく、そこだけ回収するように変更する
後はその情報をまとめてからDPする
上記のスパソの回収漏れと、血迷ってKMPでO(M|S|)なのを出したのを含めて4WA吐いた
後で解説を聞いてトライさえ組めれば文字列長最大200だから各開始地点につきたかだか200しか探索しないと聞いてなるほど～～と思った(1パターンごとの文字列長制約をあまり大事だと思っていなかった)
E
Cが終わった時点で2時間10分ぐらいだったので軽くあきらめモード
見た感じ刺す位置を固定しさえすればあとはN個の肉は独立に考えられるのでそれぞれO(logL)ぐらいで「位置kに串を刺す時の最適解」が求まれば嬉しいなぁとか思った
ただコストが2次関数で駄目だ～～～ってなっていた
この辺で予選BのDEを思い出してsegment treeなんじゃないか？とか思ってしまう
が、ここらへんで時間が終わる
ちなみにFも読んだけど無理
解説
Aの解答例としてグリッドグラフに斜線入れたやつを出される。random_shuffleで倒せるか不安になった
EでL個のクエリをO(LlogL)で処理すればいいというのを聞いて昇天した
Fは聞いてて本当に天下の人間向きの問題なのかと疑った
AB結果・表彰
懇親会会場に移る。
A問題とB問題の最終結果が発表された
http://tenka1.klab.jp/2016/stands/
下から順に発表していく感じで追い抜いたりするのが面白かった
乱択で張れるだけ張ったケースは17撃墜、random_shuffleは11ACでした
で4完の中では1位の14位に。最下位スタートだったので嬉しい
A問題全撃墜ケースはドロネー三角形分割らしい。不可能。
B問題上位はしっかり枝刈りDFSをしていたらしい
ちなみにこの後懇親会中ずっとA問題ケースをプロジェクターで映されていたのですが多分僕のケースが一番緑々してて目に優しかったと思います(頂点がオレンジ、辺が緑でビジュアライズされていたため)
表彰はめっちゃ拍手してました
懇親会
🍕🍕🍕🍕
なんかすぐに🍕が消えた
あと適度におしゃべりをした
感想
緊張してた割にはかなり楽しめた気がする
来年はそもそも予選通過できるか怪しいけど賞金を目指したいなぁ
KLabの人へ
エナジードリンクごちそうさまでした
モバイルバッテリーも結構重宝するので助かります
あと本戦会場後ろにあるスクフェスの折りたたまれたパネルがすごく気になりました
