ACM-ICPC 2016 アジア地区予選つくば大会 参加記
2016/10/15~16 にかけて ACM-ICPC アジア地区予選つくば大会に参加しました。
行き
車で行きました。
何故新幹線ではなく車かというと、こちらの画像をご覧になればよくわかります。
１日目
オフ会。
今年はホテルが東横インで本当に最高だった。（昨年比）
東横イン最高！
— さて (@public_sate) 2016年10月15日
一番好きなホテルです pic.twitter.com/Bu3aSE9FmE
運転して疲れたので結構早く眠れた。（ホテル行く前に迷ってARCに間に合わなかったというのもある）
二日目（コンテスト本番）
実は前日まで風邪気味だったのだが、朝起きたらコンディションはわりと良さげ。ジャージで朝食を食べていたらDQN呼ばわりされた。
だいたいのことは怒髪さんがやったので自分は自分のしたことを書きます。(問題のネタバレを含む）
B
問題を読む。長い。
読解に凄く時間がかかって、問題を解き終えた時点で既にABDが解かれていた。
しかも、Bを解いた順位表で瞬間一位になって盛り上がった。(開始42分)
F
問題はさっきより読みやすい。
AがBの子孫であるかどうかをチェックする問題。
n個の文献が与えれて、各文献でm個の"xの子孫がyである"という情報が与えられる。
各文献で与えられる情報は本当or嘘で、嘘の文献の情報は必ず正しくなく、本当の文献の情報は必ず正しい。
このとき、Aの子孫がBであることで矛盾が発生しないような文献の真偽の割当が存在するか判定して下さい。
"aの子孫がbである"情報を見たい時は、"aの子孫がbである"と"bの子孫がaでない"をqueueにpushして矛盾判定と文献の真偽書き込みをする。
"aの子孫がbでない"情報を見たい時は、そのままqueueにpushするBFSっぽいことをして最後にDAG判定すれば解けると思い「解けます」と言ってとりかかるが…
まず、TLEがでて、直してもWAがでる。冷静に考えてその時点で通してるチームが1・2チームくらいしか無い問題がそんな簡単なわけがない。
悩んでるうちにEやGも怒髪さんが解いている。
しばらくして、ひどい誤読が発覚しそもそも入力が間違っていることに気付く。それで再考察して書き直してみるとやっぱりWA。
悩んでいるうちに怒髪さんがJも解き終わり、一緒に考えようとなる。
問題の本質が発覚、各文献に書いてある"aの先祖がbである"をqueueにpushするだけだとだめで、それによって間接的に判明する先祖の情報もわからないとダメ、これにはDAG動的構築していい感じにマージしていく必要がある。これを愚直にやると全体のO(V^4)になってしまう（Vは頂点数でV=300)。V^3に落とす必要があり、再び悩むのでトイレに行く。
トイレから帰ってきたら怒髪さんがこれでいけそうみたいなことを言い始めるのでそれを書く。WAが出るが、細かい所をよく見るとバグが埋め込まれているので直す。
AC(158分)
やっぱ怒髪神。
結果 4th place!!
やったあ！（しかし、企業賞なにも貰えず壇上に立たせてもらえなかった）
（その後、KLab様から大容量充電器をいただきました！アリガトウございます！！
夜は、懇親会でいろんな企業の問題を解いていた。（indeedのゲームに勝って29名以内にはいったのは嬉しかった）
二次会でお疲れ様会をした、ビールがうまい。
三次会でカラオケをした。(with @asi1024,@n_vip,@kyuridenamida)
選曲の世代が滅茶苦茶で面白かった。
帰り
カレーうどんzeyoという店に行きました。
早食いで記録出せば2000円お食事券とか書いてあって某限界超越怪獣に挑戦してもらいたいと思った。
乙カレー
感想
ICPC最高！一番好きなコンテストです！ホテルも良くて運営も最高でした！
