ACM-ICPC 2016 アジア地区予選つくば大会 参加記
2016/10/15~16 にかけて ACM-ICPC アジア地区予選つくば大会に参加しました。
行き
車で行きました。
何故新幹線ではなく車かというと、こちらの画像をご覧になればよくわかります。
1日目
オフ会。
今年はホテルが東横インで本当に最高だった。(昨年比)
東横イン最高!
— さて (@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最高!一番好きなコンテストです!ホテルも良くて運営も最高でした!
AOJ 2335: 10歳の動的計画 10-Year-Old Dynamic Programming
問題↓
10-Year-Old Dynamic Programming | Aizu Online Judge
問題概要
- 格子があります。
- 右と上しか進めません。
- ただし、ちょうどK回だけ寄り道(左or下に行くこと)します。
- (0,0) から (N,M) に辿る道は何通りあるでしょう。
- (0,0)より左下には行くことができない(マイナスの座標へはいけない)
解法
続きを読むACM-ICPC World Final 2016 Phuket, Thailand 参加記②本戦編
結論から言うと、 77/128 位
①でのバカンスっぷりと打って変わって激冷ました。
4日目はprcaticeをしておしまい。
時間があったので、初日に仲良くなった海外スマブラーとスマブラをしていました。うぇい。
本番、5日目。
まず、最初に僕が flymake を書きます。
前日の夜に3回flymakeを複製してから寝たので大丈夫だろうと思ったら
(の対応が取れていないバグが入り込み時間がかかってしまった。(本当に申し訳ない)
準備をしている間に既にFAが取られているので解かれているC問題を読む。
WF唯一のやるだけ枠だったのでさっさと通す。
それ以降、何があったかをぼくはよく知らない。
二問目Lは普通に通される。
三問目、G問題がdohatsuさんとzukkyさんが一瞬で解法だしててzukkyさんが実装していたがWAを連発。
誤差ゲーが止まらない。
四問目K、よく分からないけどdohatsuさんが実装しててまぁ大丈夫だろうと思いきやWA。
2完のままよくない流れが続く。
193分経過
G問題をAC!EPSを消したら通るという謎現象
流れが変わり、続いてK問題もAC
そして、解いている人数の多いEを真剣に考え始める。
―が、無理
誰も分からず
B問題に移るとdohatsuさんの考察で問題がDPにまで落ちる。
DPの高速化ができそうということで実装するが、嘘高速化な気がしてよく分からず定数倍改善に方向を切り替えるも時間切れ。
結果、4完でした。
感想
ペテルブルグと上海交通大学の頂上決戦は見ていた楽しかった。
世界やばい。
https://icpc.baylor.edu/scoreboard/
今まで一番国際交流をした気がする。スマブラは偉大。
象にも勝てない、波にも勝てない、コンテストでも勝てないと己の弱さを知れた。
WorldFinalの待遇は最高。
関わった全ての方へ、ありがとうございました、お疲れ様です。
チーム名との怒髪さん、来年も頑張りましょう!
そして、引退するズッキーさん、本当にお疲れ様でした!
ACM-ICPC World Final 2016 Phuket, Thailand 参加記①観光編
興奮冷めやらぬ三日目朝、これを書いてます。
二日目である16日はほぼ自由時間だったので今回はそれについて書いてきます。
以下大量の写真
- コーディネート
今年の夏は、ICPCコーデで決まりッ pic.twitter.com/6pPKx5iZ4z
— さて (@public_sate) 2016年5月16日 - 青い海、白い砂浜
全方位型バカンス (@ Le Meridien Beach Resort in Phuket) https://t.co/GLN3roQuiy pic.twitter.com/Rv0SXkIwc2
— さて (@public_sate) 2016年5月16日 - プール
- パターゴルフ
コードじゃないゴルフ pic.twitter.com/ax9B9XzOHd
— さて (@public_sate) 2016年5月16日
- お昼ごはん
- プール
- マッサージ
- バスケ
- プール
- スマブラ
ここから帰ってきてから書いてます。
三日目はプーケットの観光地、FantaSeaに行きました!(そもそもプーケットが観光地)
午前中はIBMのオープニング
ACM-ICPC ダークサイドに堕ちる#ICPC2016 pic.twitter.com/honzMaJvSp
— さて (@public_sate) 2016年5月17日
午後はFantSeaでオープニングセレモニー
リゾート地の次はTHE観光地みたいなとこきた pic.twitter.com/XfR652mNN3
— さて (@public_sate) 2016年5月17日
幼稚園くらいのとき以来はじめて象を見ました。
象が想像以上に早くてびびった。
撮影は禁止だったのですが、ショーも見ました。
内容は『象さんにかければ人間なんてけちょんけちょんやぞ』という感じ。
空飛ぶ人間と瞬間移動する人間を初めてみました。
きゅうりさんが醜い動画をアップロードして日本の恥・public_sateを晒しかけました。
向こうのおみやげは結構安かったです。
②本戦編へ続く
AOJ : 2256 Divide the Cake ケーキ分割問題
Divide the Cake | Aizu Online Judge
問題概要
- W*Hの平面にN個の点があります。
- 左端から右端に線分を一本ランダムに配置したとき点を半々に分割できる確率はいくつか
解法
続きを読むAOJ 1310 : Find the Multiples
Find the Multiples | Aizu Online Judge
問題概要
- N個の要素からなる数列Aが与えられます。
- 各要素は0~9です。
- [i,j] における数列を1つの数字と見た時 Qの倍数になるような
iとjの組み合わせはいくつあるでしょう。
解法
続きを読むAOJ 1308 : Awkward Lights
Awkward Lights | Aizu Online Judge
問題概要
- N*Mのマスがあります。
- 各マスにはライトが設置されており 1 がON、 0 がOFFです。
- あるマスのスイッチを押すとそのマスのライトとそのマスとマンハッタン距離がDであるようなマスのライトのON/OFFが反転します。
- マスをいくつか押して全てのマスをOFFに出来るか判定してください。