ACM-ICPC2017 国内予選 参加記

土曜日のうちに参加記を書こうと思ったけど二日酔いでダメだった

1. チームメンバー

femto:

紫コーダー(CF)。M2。去年は地区予選進出。フローと実装の重い問題を担当。

conf:

黄色(Atcoder)。B4でICPC参加は3回目、地区予選は未経験。印刷、考察、めんどくさい問題の実装と幾何を担当

fooractal:

青色コーダー(Atcoder)。B4でICPC参加は3回目。簡単な問題の早解きを担当

ちなみに３人とも別々の研究室に所属している。

去年のチームRINKAKU NO DANPENとチームnishiyonの残党が合流した結果いろいろあってチーム名がnishiyon NO DANPENになった。

2. 前日まで

4月までは個人でAOJ-ICPCを埋めたり、苦手な分野を練習するなどした。

4月末から大体1週間に1回のペースでVirtual Arenaを使って適当な問題セットを他のチームと一緒に集まって解くというのを合計10回ほどやった。

今年の目標は電通大から2チーム地区大会に進出することで、そのためには1チーム目が5完、2チーム目が4問早解きをすれば良いだろうという予測からAOJ-ICPCの黄色以下の問題を多めに突っ込んだ問題セットを作った。場所は学生が自由に使えるロビーや所属する研究室のゼミ室を勝手に使った。学内には土日に入れて飲食できてWi-Fiが入る環境というのがあまりなくて難しい。本番の環境にできるだけ合わせるためにPCは1台だけ、問題は各チーム1部ずつ刷って来て配って3時間とか時間を測って練習した。本番で確実に4完できそうだったのはうちのチームくらいで、他に2チームがもしかしたら4完できるかもしれないというレベルに達したところで時間切れ。模擬国内予選ではうちのチームだけが4完で他は3完以下だった。

3. 当日

多めに寝ておこうと思って2度寝したら起きたのが11時だった。いろいろと時間のやりくりをして昼休みにリハーサルに参加。その後3限の輪講に出た後、4限の時間に行われた修士の中間発表をちょっとだけ見に行ってから学内会場の計算機室にこもって必要なライブラリを刷ったり、エディタやデバッガの動作確認をしたりして開始まで準備をした。

チーム内で使用するキー配列、エディタ、コンパイラがバラバラなのでコンテスト中にコーダーが交代する際にはキーボードを交換して設定を変更したりする必要があり、いろいろと面倒かつリスキーだったけれど、統一するほどの時間的な余裕も無いので諦めた。

コンテスト開始5分前に大体の準備が完了して、コンテスト開始と同時にとりあえず問題の印刷をプリンタキューに突っ込んでA問題を見た。クソ簡単な問題だったのでそのままfooractalに投げて自分はプリンタへ。なぜか待てども待てども出てこない。他のプリンタを割り当てられたチームも同様らしく、仕方が無いので席に戻るとfooractalがA問題をSubmitしていた。5:41にAがAC

印刷を放置してfemtoさんが簡単だというB問題を僕が書くことに。最初にstringが全部同じかチェックして、1文字だけ違えばCLOSE、それ以上違えばDIFFERENT、という風に聞いて、コードを書き始めたがなんかサンプルに違和感を感じて問題文を読み返したらなんかクソややこしい奴と判明。まあそんなに変わったことはしていないのでサンプルが一致するようにアドホックな汚いコードを書いて投げたら通った。26:27にBがAC。

C問題の解法を生やしたfemtoさんに引き継いで、僕がBを書いている間にいつの間にか問題の印刷が来ていたのでそれをfooractalを見ながら次に解く問題を決めることに。直感的にD,F,Gが解けそうな問題と思ったので、とりあえずDを読み込む。まず自明なO(n*2^m)のDP解が思いついたのでこれを指数時間のままで計算量を圧縮できないかと2部グラフを書いたりして考察。なんか半分全列挙っぽいアプローチができればうまくいきそう。というところまで行って行き詰まる。なんか極太の文字でかかれた

\begin{align*}
1 \le n \times \ m \le 500
\end{align*}

がどう考えても重要なヒントに見えるので、それが持つ意味を考える。まず500という数字を見るとその3乗まではOKという意味のように見えるけれど、さすがに多項式時間アルゴリズムが生えるはずは無い。じーっと眺めていて、nとmのどちらかが22以下であることに気づく。とりあえずm<=22の場合のDP解法のスケッチを書いて、m>22の時どうしようと悩んでいたらnに対して2^n通りのbruteforceができるとfooractalからツッコミが入ってとりあえず解法完成。コード書く？とfooractalに聞いたら嫌がったので、自分が書くことに。femtoさんがC問題を通すのを待って交代。43:57にCがAC。

僕がD問題をゴリゴリと書く間に、残り2人が解けそうな問題の考察を始めるも、なんかDがバグる予感しかしないのでペアプロを頼む。一応サンプルが通ることを確認して投げたらWA。よく確認したらbruteforce部分で$m\ge64$のときにオーバーフローするバグがあったので修正して投げた。1:16:28にDがAC。

時間的に5完余裕と思われたので、次の問題を検討する、Gは右手法で解けそうだったが、実装をどうすればいいかよく分からず、Hはおそらく全探索だろうというのは確実だったものの、時間配分的にこれに行くのはどうよという感じで、実装が軽そうなFに走った。
femtoさんがひたすら紙上でシミュレーションをして解法を立てて、僕が実装するもサンプルが合わず、検証すると嘘解法と判明。この時点で残り1時間を切っていた。Fを切り捨てられず、3人でFを考察。時間切れ15分前にシミュレーションしながら枝切りDFSするとO(n)で解けることに気づいて実装するも、バグが取りきれずに時間切れ。

結局、4完になってしまった。GとHは解法が見えていたから、Fの考察を任せて実装を頑張った方が良かったんではないかと反省。分業がうまくいってなかった。

4. その他

電通大からは4完が2チーム出たけれど、順位的にはうちのチームしか地区大会には行けなさそう。終了後の打ち上げでDの解法を他のチームに解説していたら、もう一つのチームがD問題をBFSで2分探索(two minutes search)して通したと聞いて呆れた。公式の講評で言及されるかどうかが楽しみ。

AOJ2306 Rabbit Party

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2306
2011年のJAG夏合宿問題らしい。出題者の解説スライドなど

入力：
n匹のウサギと、そのウサギmペアの仲良し度が与えられる。仲良しじゃないペアは仲良し度0とする。
つまり
n頂点完全無向グラフ$(V,E)$上のm辺の重み$f{:}  E  \to \mathbb{N}$が与えられる。重みが与えられない辺は重み0と見なす。

出力：
それぞれのウサギの幸せ度はパーティーに参加している他の参加者との仲良し度の最小値。もし仲良し度0の相手がいると自分も相手も幸せ度0になる。コワイ！
参加者の幸せ度の総和が最大になるように参加者を選んで、幸せ度の総和を出力せよ
つまり
\begin{align*}
    \max_{S\subset V} \left\{ \sum_{v\in S} \min\left\{ f(\left\{u,v\right\}) | u \in S , u \neq v\right\} \right\}
\end{align*}

制約：
\begin{align*}
1 \leq &n \leq 100 \\
0 \leq &m \leq 100 \\
1 \leq f&(e) \leq 1,000,000 \ \ (\forall e \in E )
\end{align*}

考察：
もし選んだ頂点からなるクリークが重みゼロの辺を含むとすると、その両端の幸せ度は0
どちらかを外した方がマシになるので、最適解のクリークは辺の重みが全部非ゼロ。重みが非ゼロの辺の本数が100しかないので、最適解の頂点集合の大きさは高々14。
という数学的事実があるがここでは無視する。

手順：
すべての重みが非ゼロの辺 $e \in E$に対して次の貪欲アルゴリズムを適用し、その最大値を求める。
1. eの端点2つを参加者の集合Sに入れる。
2. $V-S$の中で、$S \bigcup \{ v \}$の幸せ度の総和が最大となるような参加者v*を探す
3. Sにv*を追加したときに幸せ度の総和が増加するならSにv*を追加し、Step2に戻る。
4. 追加して幸せ度が増加するようなvがなくなったら終了し、幸せ度の総和を返す。
計算量は$\mathrm{O}(mn(m+n))$かな？

実装：

感想：
間違っている気がするけれど、ACしたし、間違っていることを証明することもできなかったし、よく分からない