ACM-ICPC 2016 Daejeon大会参加記 - 衛生のゴミ箱(二勝目)

出発

会津を11:08の電車で出ようとしていたはずだが怒髪さんが来ない。

kzy先輩と2人で行く成田を目指す。

成田にて一時間遅れで怒髪さんと先生と合流。めでたしめでたし。

ところで、最近（ここ数年）キャリーバッグを走らせる度にキュルンキュルン鳴ってうるさかったので油をさしてもらったところ大変快適になった。

17:30~

出国検査を受ける。

「こちとら何回検査受けとんじゃひっかからんやろ」と高を括っていたら制汗スプレーをバッグに入れっぱなしだったのを忘れていてsampleケースで撃墜された。

18:00~

出国→フライト
飛行機ではゴースト・バスターズ（新しいやつ）を見た。いい感じにコメディ映画。

21:30~

韓国に到着。あまりの近さに感動するも実際はこの後の移動が長かったりする。
リムジンバスという称すると良さげなバスに乗って快適にホテルへ向かうこと約2時間ちょい

24:00頃

ホテルへ到着（東横イン）。
最初に見かけたコンビニが締まっていて衝撃を受けたが、その店は昼でもやっているように見えなかったのでそういうところなのかもしれない。
その後、ホテル付近でちゃんとやっているコンビニを聞いて恒例のコンビニ散策を行う。（フロントのお姉さんが日本語しゃべれて神）
コンビニに入ると嗅いだことのない異様な臭いがした。
もっとも既視感のある表現をすると「すっごい遠くに生ゴミがある臭い」
水とアイスを買った。おいしい。
その後、部屋でムーミン（英語）を見て寝ました。

Practice

プラクティスセッションの日になりました。
集合が昼でだいぶ余裕があったので観光しようという案もあったが昨日の旅路の疲れで普通に昼間で寝てました。
お昼ごはんをどうしようか考えましたが、KAISTの学食に行ってみようということになりました。

KAISTの学食でビビンバを頼んだのだが、出てきたのは生野菜とごはんとコチュジャンがそれぞれ単体で出てきた。
どうやらこれらを混ぜて食べるらしいのだが、本当に生野菜とご飯とコチュジャンを混ぜただけの味がして実質味の要がコチュジャンに依存しておりコチュジャンを大量にかけないと味がしないのだがかけすぎると辛くて食べれないという代物だった。

その国の料理を味わうのに学食は適さないということを知った。

昼になって京都の人たちと合流して話を聞くと、どうやらホテル付近の料理はだいたい当たりだったらしく我々の選択肢は失敗だったことに気付いた。

opening ceremony ~ practice session

英語かと思いきや韓国語だった。
あとから聞いた話だとどうやら韓国語と英語を交互に話していていたらしいが唐突に始まる"You"と唐突に終わる"ニダ"が多すぎて途中でどっちで話しているのか分からなくなり就寝した。

practice sessionはキーボードの動作確認や、ジャッジの環境の確認などをした。
Sample Inputがファイルで置いていなかったりジャッジ環境の詳細情報が載った紙が無かったり日本と比べると所々不親切な仕様ではあった。
コンテスト自体はそんなんですが、スタッフはみんないい人でした。
地味にPractice sessionでは3位でした。

晩御飯

京都の人達と夕飯を食べに行きました。
いろいろオススメを聞いて回った結果、東横イン近くのBBQってことろがまぁ美味しいらしくそこに行きました。（主にチキンの店だった）
まぁ美味しかったです。

ホテルに帰った後、一人でお土産を買いにてきとーにその辺を散策しました。
Home Plusっていうショッピングセンターみたいなのを発見してそこでいろいろ散策しました。
韓国海苔を爆買いしました。
この頃になると「カムサハムニダ」をマスターして、迷ったときはガバガバ英語で訪ねた後に「カムサハムニダ」でお礼を言うコンボを重ねていました。

その後ホテルに帰り、就寝。

Contest

コンテストの話は例のごとく怒髪さんが細かく言ってくれるはずで僕の視点の話を書いていきます。

朝食をACした後、タクシーでKAISTに向かいます。
タクシーの運ちゃんが日本語が分かる（好き？）みたいで話しかけてくれたのですが、運転中に急にスマホの写真アルバムを見始めてなにやっとんじゃと思ったら、警察官の写真を見せてきて「これ日本の友達」と教えてくれました。
いや、友達に捕まるぞお前。

Contest Start

開幕の動きは、僕がキーボードを自前のHHKBに変更し怒髪さんが環境(flymake)を整える。

その間にkzy先輩が問題を読む。俺も読む。って感じです。

自分はまずB問題を読みました。
概要：Nチームで総当たり戦を行います。i(1~N)番目のチームの勝利数が与えられるので、そのような組み合わせの総当たり戦の表が作れるか判定して下さい。( N <= 10,000 )

よくある、一番負けが多いやつと勝ちを結んでいく貪欲のあれだと思い N^2 logN を実装しました。
普段ならN = 10,000 間に合わないと判断してるところでしたが、如何せん練習セッションでO( 10,000^2 log(N) )くらいのが普通に通ったので韓国のジャッジはガバい！とか勝手に思い提出しました。

TLE

これが良くない流れの始まりだったのかもしれません。

順位表を見てみるとG,I,Lがたくさん通されていた。
自分はGを、kzy先輩はIとLを処理しました。

一方で、珍しく怒髪さんがC問題でTLEを出して唸っているので
こちらもN^2が通らなくて困ってるBを投げてそっちをしてもらうことにしました。
その間にCの計算量がO(Nlog^2(N))らしかったので、logを一つ落とす方法を書いてAC！
怒髪さんもBを再考してAC!

新技「Swapping Accept」誕生の瞬間である。

再び順位表を見るとHがちらほら解かれ始めていたので、トイレに行きながら考えることにしたら、少し希望が見えてきた。
概要：木があります。
　　　頂点にはsource側とsink側があり、辺には流量の制約があります。
　　　全てのsinkに必要なだけの流量を流せるか判定して下さい。
　　　source側から湧き出る水の量も決まっている。

葉からいい感じに見ていけば子に流せるなら名一杯流す、そうでなければ親に助けをこうみたいなことを考えるも実装に凄く手間取る。

---- この行間で怒髪さんがDとEを通す -----

手間取っていたらいつの間にか終了5分前になっており、個人的にはあとif文を一個追加すれば通るみたいな状況になっていたら唐突にディスプレイが真っ暗になる。
急いで挙手するがスタッフがなかなか駆けつけてこずすっごい困る。
どうやらPCの電源が落ちていたようで、何故急に電源が落ちたのかは一切不明。
再びPCが起動した頃にはコンテストは終了していた。

ち～ん

オシマイケル