ACM-ICPC2013 アジア地区予選嘉義(台湾)大会参加記

ICPC2013嘉義大会に参加してきました. 台湾です. FCCPC_alphaというチームでした. 結果は大学別5位でした. 全体ではまだわかりません. 2013/12/07追記: 全体では10位でした. 最終結果

凍結される前のstandingsは公式のものは消えていましたが, IRUNさんが公開しているものがありました. https://dl.dropboxusercontent.com/u/48151090/temp/taiwan.html

-0:05 問題発生

スタッフが本人確認に来るも, うちのチームのだれも身分を証明できるものを持っていない(持ち込み制限に引っかかると思ったため). また, そのとき英語がうまく伝わらず日本語で話してくださいと言われる(日本語話せるスタッフ多い). 急いでコーチを探すも観客席には見当たらず開会式とかやるところにスタッフと一緒に行く. この時すでに開始1分前ぐらいになり, スタッフにとりあえず戻るように言われる. 戻ると9:32ぐらいになっていて, 席につくと同時にコンテストが始まった. たぶんうちのチームを待っていてくれて, 非常に申し訳なかった.

~0:28 A Accepted

これの前にBをやっていた. Bはマンハッタン距離でやる. 縁を回って黄色と青が交互に来ていたらダメ. 一回投げるもWA. Aは題意を全く知らないのだが, 2分探索で通したらしい.

~0:33 B Accepted

黄色と青がすべて1行(列)に並んでいる場合は+2するのを失念していた. 修正して提出. AC

~0:52 G Accepted

周囲を見ると青い風船がやたらと上がっていて, ずっとBだと思っていたのだが, PCのデスクトップにある問題と風船の色の対応をよく見るとGであることに気が付きGを解くことに. ソートしてやるだけではとなり, まあ通してるチームも多いし大丈夫だろうと提出. AC

~1:11 F Accepted

問題を見た瞬間, 配列アライメントだやるだけだと気づく. ぱぱっと実装し提出. AC 実は東工大の情報工学科には生命情報解析という講義があって, そこでさんざん同じものをやらされていたので瞬殺だった.

~1:52 C Accepted

CとDを平行して進める. Cを先に提出するもWA. デバッグしてる間にDを進めていたが, すぐにCがlong longにしていないだけだと気づいて#define int long longして提出. WA ansの初期値を1e9にしたままだったので修正して提出. AC

~1:56 D Accepted

Dは多項式の逆元を求める問題だったらしい. 気づいたらAC

~2:25 E Accepted

Nクイーンなので探索する. すぐに終わって提出. WA N=1の場合がうまく探索できていなかったので修正して提出. AC

この時点ではまだstandingsを確認していなかったが, TwitterのTLをさかのぼってみたら3位だったらしい. しかしこのあとはAC取れてないので順位は下る一方.

~3:00ぐらい submit I

Iは大きい数は明らかに作れないがそれだけじゃないよなあ, わからないなあとなる. ソートしてbをaに近づけるという操作をしてやってみる(実は行列を複数回掛けてもいけるのではという仮定のもと). サンプルは合うので提出. WA やっぱ無理と諦める.

終わってからwakabaに話を聞きに行くと, 大きい数は明らかに作れない. それだけを書いて提出したら通ったらしい. なぜそれで十分なのかはわからない.

~3:30ぐらい Kについてclarを投げる

Kは最小費用流ではということでやるも, サンプルの最後だけ合わない. 何が何だかわからないのでサンプル間違ってるぞとclar投げる. 返事はサンプルは合ってるよとのこと. 普通に誤読. 結構注意深く読んだつもりだったのだが…… 結局誤読に気がつくと無理ゲーだったので捨てる.

~4:20 Jをひたすら進める

ピースはちょうど2個という制約から2ｰSATを疑う. 他に方針が立っているのがなかったのでKと平行して進めていた. しかし実装がやばいことになってバグが取れない.

~5:00 Hを進める

Hの囲まれるやつが(1,1)固定だと残り1時間ぐらいで気がつく. Jが無理そうなのでHに切り替え. バグる. Yellow Yellがなんか喜んでいて8完されていることに気づく. 修正が間に合わず終了.

終了後, wakabaに何完したか聞きに行くと8完と言われてやばいと思う. 結局wakaba, ~shiokawa, Yellow Yellが8完してたらしい.

まとめ

HとKを誤読してしまったのが非常によくなかった. 特にHは時間があれば絶対に通せる問題だったのでよくない. ただ7問通す速度はよくて, 非常にうまく回っていたと思う. 制約をすべてメモるようにしていたおかげか, 会津みたいなミスはなかった. 次は誤読対策を真面目に考えなければいけない. 英語力も足りない. WA多いので減らさなければならない. WAについてはテストケースとか考える力が圧倒的に足りない. SRMとかまじめにやるのが良さそう.