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したし、間違っていることを証明することもできなかったし、よく分からない

JAG夏合宿2016 参加記

国内予選落ちしたくせにJAGの夏合宿に行ってきました。
みなさんお疲れ様でした。

0日目

大学でJAGの夏合宿の存在を知る。

過去に参加した先輩が、ぼっち参加は辛いから複数人で行った方がいいよ、と言っていたので、とりあえずチームメイトに声を掛けて調整
→国内予選の時のチームメンバー３人(僕と@fooractalとのし(@llll_))で参加することにした。
他に予選に通った先輩方２名も参加してUECからは5人参加。実力不相応な大所帯。
他にも申し込み締め切りを忘れてたとかそういう理由で行きそびれた人が居たらしい。
申し込み時にtwitter垢を晒すかどうか躊躇して書かずに申し込んだら、配られたしおりにおよそ9割の参加者のtwitterIDが晒されていて唖然とした。とりあえずリストを作って全員をフォロー。

1日目

朝から支度をして12時前くらいに調布を出たら途中で昼飯を食って行ってもかなり早くにオリセンに着いた。調布から近すぎて宿泊する意味あるのかなと思う。集合場所で運営が用意したWi-Fiにつながるかテストしたがかなり不安定で細かったのでオリセンでは自分のiPhoneの回線を使うことにした。自己紹介では何を言ったか覚えていないが、他の人がひたすら自分のレートのことばかり話すのが不思議だった。

夜の懇親会では、"直接あったことはないけどtwitterでは相互フォロー"みたいな人たちが集まって盛り上がっていたけれど、そもそも自分はICPC以外のコンテストにあまり興味がなく、いわゆる競プロクラスタに属していたわけでもないのでどうも馴染めなかった。

2日目

なんか同室の人々がやたらと早く寝て早く起きて6時半には全員起きていた。健全。

オリセンでの2日目のコンテストはfooractalがPCを持ってきてないとかいう事案があり、まともに使えるのが僕のUS配列のMBPRだけで困った。厳密にはICPCルールに違反してるけど、外付けのJISキーボードを刺して利用。それでもやっぱり僕以外には使いにくいのでコーディングの大半を僕がやることに。4完してそのうち3問を解いた。

http://jag2016summer-day2.contest.atcoder.jp/assignments

K:

最初に手を付けて簡単なDPっぽいと思ったが、ルールの誤解に気づいて後回し

C:

なんか簡単そうだからのし君に投げて様子を見たら謎の場合分けを始めていたので、取り上げて等差数列を使った解法を編み出してサクッと実装してサンプルも通ったからSubmit、したらなぜかRE。再帰も配列も無いのにREということはゼロ除算か！？と思ってソースコードを印刷して紙デバッグに入るがやっぱり分からない。

Hの後で色々と手を尽くしたらなぜかREが取れてAC(2:18)。

H:

Cで詰まっていたらfooractalが解けたというので計算機を譲って放置。DFSらしい。なんかバグらせていたので途中デバッグを手伝って無事にAC(1:53)。

D:

僕がCで詰まってfooractalがHを書いている間に僕がDの解法を思いついてCの後でゴリゴリと書いてAC(3:54)。普通にグラフを作ってDFSするだけ。最初は何回も分数のかけ算を繰り返す必要があり、long long intでは収まらない程度にまで分母分子が大きくなるんじゃ無いかと思っていて、素数指数表現で数値を持たせて地道に素因数分解していたらコードがやたら長くなってしまい実装に時間が掛かった。終わってからgcdを使えばいいことに気付いた。

I:

解いたチームの数だけ見てこの問題に着手することに。貪欲法でやるだけ。簡単だが問題文の誤読があり、書き直しで時間を消費。なんとかAC(4:45)。

Cの謎のバグで時間をロスしたのが痛かった。相談しながら問題を解くほどの能力がチームに無いので無駄に誤読や回り道で時間を費やしていたのが課題。

３日目

LINE本社にて模擬地区予選。なんかリッチな感じの会場ですごかった。

５時間掛けて2完に終わってしまい凹む。

A:

すごく簡単そうな問題だったのでさらっと書いて出したらWA。なんでやねんと思ってよく問題文を読み返したら数列が単に昇順であるにのみならずconsecutiveでなければならないと書いてる。どういう意味かと思って持ってきた辞書を引いても載っていないので、おそらく連続していればOKだろうと判断して書きなおしたらAC(0:29)。

B:

簡単な探索問題らしい。fooractalに任せてAC(0:37)。

D:

その後自分は簡単そうなD問題に着手。)))(((の形には行きついたもののの、反転数の大きいものを崩すのではなく、複数の文字列を繋ぎ合わせて出力するという方向に行ってしまいWA。サンプルと半分くらいのテストケースには通るので、入力がデカイ時の桁あふれかと思っていたら失敗した。

C:

Dの紙デバッグをしている間にfooractalに投げたらなんかクソ長いコードを書いていて、さらに見ていたら一回捨てて１から書き直してまた詰まっていて、仕方なく僕が書くことに。問題のルールを誤解していてコードが完成せず終わった。後で解説を読んでも働いてる人が脱退した場合にその人についてニートになったと出力をするべきなのかが曖昧な気がした。

結果的にはDのミスに早く気付いていればCも最初から全部自分で書いて4完できただろうと思ったけど、それってチームの意味が無いような…問題のデバッグとか考察を２人以上でやればいいんだろうけど、説明しても難易度的に僕しか扱えなかったりして難しい。

夜にAGCに出てA,Bだけ解けた。

4日目

のし君が別のイベントに参加するために離脱。

KLabの会議室で行われた模擬コンテストでは人数合わせのために紺青(@konjo_p)さんとチームを組む。レベルが違いすぎて申し訳なさしかなかった。

チームで4完。自分では0完

A:

最初自分が担当。やるだけ問題なのだが、計算量の見積もりを誤っていて無駄に難しいこと(値が最小のキーの取得と値の更新をO(logN)でやる)をしようとしてコードがスパゲッティー化して詰んだ。1から書き直すように促されたのを交代しろということかと勘違いして紺青さんに丸投げ。

弁当を食べずにいたら空腹が限界でまともにコードを書ける気がしなかった。時間配分的には大きな失敗。

B:

鬼畜な幾何問題ということが分かったので放置。

C:

自分がAを書いてる間にfooractalが解法を考えたので計算機を譲ったら一発ACしてた。どういう問題なのかは謎。

D, L:

いつの間にか解かれていた。詳細不明。

全然役に立てなかったけど、チームで競技プログラムをやってる感はあった。コーダーは他のことやっちゃダメとか怒られたのが新鮮だった（普段は実質的に2人ペアなのでどちらかのコーディングに割り込みしないと何も相談ができない）。

感想

運営の人手が足りてなくて本当に大変そう。強い人ならソロで参加しても楽しそう。逆に弱い人にはたとえ複数人で参加しても問題解けなさすぎて辛そう。僕らみたいに競プロサークルがない大学の場合には、チーム戦のやり方を知ることができて問題解けなくても勉強にはなった。