FCCPC

FCCPCについてお伝えするブログ

ACM-ICPC Asia Tokyo Regional Contest 2014 参加記

記録: hadrori

問題(AOJ)
結果

2014年10月19日にICPCアジア地区予選東京大会がありました.
FCCPC_Aliceの結果は全体8位, 大学別7位でした.
終始黄色いパーカーを着ているチームだったのでだいぶ目立っていたと思います.
とりあえずコンテストとその前後の参加記を書きます.
記憶が曖昧なので若干時系列が前後していたり内容が正確でない部分があるかもしれません.
空行でだいたい場面が変わってます.

コンテスト前日

sample inputをwget -rで一括ダウンロードできるとおさけーさんに教わる.
完全にプロ.
チーム紹介はスライドをトレンドマイクロの時の1ページ目だけ抜き取ったやつを提出していたため完全に手抜き.
ライブラリの整備が終わってないのでさっさと帰りたかった.

コンテスト当日朝

小田急線が止まりFCCPCに戦慄が走る.
普通に間に合ったのでよかった.

本番

0分

とりあえずキーのスワップ, init.elとaliasを設定する.
あとwgetでinput全部落としておく.
s「選択でコピー, マウスの真ん中でペースト」
h「特殊だ」

5分

Aの実装開始
序盤は打ち合せというか練習通りなので基本無言

12分 A AC

h「Cって読みました?」
s「いやまだ」
h「よく理解できないのでちょっと聞いてもらっていいですか」

s「C分かりました. 区間をマージすればここ足すだけですね」

h「Fが通された」
s「Fは最小全域木を作るのに必ず必要な辺だって」

19分 B AC

p「何読んでない?」
h「DEHIJK」
p「E読むわ」
h「Gは括弧を反転させるクエリに対して修正すればいい括弧の一番左」

p「Eはこんなかんじだけどちょっとわからない」

25分 C AC

h「Dはなんかバウンドする物体を射出して目的地に到達できるような最小の速さ. 障害物とバウンド回数は10, 15」
s「全部試せるね. にぶたん? いらないか」
h「そんな気がするけどよくわからない」
h「Hはルンバがここにいく最短距離. 途中に邪魔なポールがいくつか立ってる」
s「グラフ作ってやるかんじですかね」
h「IはAliceとBなんとかがこんなかんじのゲームをする. スコアの合計が150程度で, 体力がクソでかいのでまあ今のチョコとスコアでうまいことDPするんでしょう. よくわかんないけど」

s「Dちょっと書いてみる. 簡単だけど式出しといて貰えますか」

h「でました」
s「あっいまF書いてます」
h「おっおう」

h「CはFAだったらしい. というか風船ここにつけるんだね. 昨日と違うから気付かなかった」

s「うーん, サンプルが合わない」
h「どうやってるんですか」
s「橋をだしてやってます」

h「ぽにょ今何やってる」
p「G」
h「いけそうなの?」
p「まだよくわかんない」

p「開き括弧を入れたいときは一番左の閉じ括弧をflipでよさげ」
p「閉じ括弧のときは((の右側を変える感じ?」
p「あ, だめだ」

60分ぐらい F WA

s「あっ」

67分 F AC

そのままDを書き始める.

s「サンプル……合ってない」
h「多分合ってると思うけど式の確認しときます」

s「よしこれであってる」
h「あってる」

xx分 D WA

時刻不明だがWA
少し修正して提出するもWA
s「サンプル通ってなぜ通らない……」
実は見間違えでサンプル通っていなかったのに気づくのは終盤.
二人して見間違えるのはクソすぎた.

p「GいけそうだからBIT実装しといてもらえる?」

s「D印刷します」
h「あっもう1部追加」

h「あっBITど忘れ. というか不安な感じだ. 蟻本取ってもらえますか」
s「はい」
h「おっ1発で開けた」
p「ついてる」

p「あ, BITじゃ無理かも. でも一応いるかもしれないから実装しといて」

h「終わった」
p「ちょっと書いてみる」

h「そういえばDの印刷まだ来ないんですか」
s「はい. スタッフに聞いてます」

s「D何が違うんだろう」
h「うーん, 1e9は足りてる?」
s「試してみよう」

s「めちゃくちゃ余裕ですね」
h「あとは精度かなあ. どこで死ぬのかよくわかんないけど……」
typedef long double numberとして提出. WA
ちょうどこのころ印刷したコードが届くが意味なし. 運営は反省して欲しい
もう一度Dを印刷
次はすぐ来た

p「区間のminをとれるBITって書ける?」
h「BITはよくわかんないけどsegtreeでならたぶんすぐ書ける」
s「逆元取れないからBIT無理では」
p「え, 書けるの?まじか. じゃあお願い」
終わってから知ったけど, こういうsegtreeのことを人々はstarry sky treeと呼んでいるらしい.
特別な名前が付くぐらいだからもっと激ヤバなデータ構造なのだと思っていた.

p「ちょっとトイレ行ってきていい?」
h「OK」

h「ちょっと不安なので少しsegtreeテストします」
s「あっはい」

p「あれ, サンプル合わない」
h「segtree間違えたか〜?」
p「あっとりあえず2分探索のバグみつけたから潰した」

p「この列とminを比較してみよう」
h「0が出てきてる. 更新が死んでるね. 直すからちょっとまってて」
更新が元の値とminとっていたため死んでいた.

184分 G AC

s「なんかたぶんEやるだけなので書きます」

207分 E AC

p「D書き直します. 入力とsimulation()だけ流用しよ」
バウンド回数を固定して障害物のギリギリを通るものを列挙して試すという方法から, バウンド回数を固定して角度を2分探索する方法にシフト.
障害物をかすめるコースが最適と疑っていないのでよさそうに見えた.
これだと最小の角度を求めてバウンド回数ごとに速さのminをとっているのでおかしい.

p「サンプルは」
h「2が合ってないね」
p「前のコードでは……」
h「あれ, サンプル2が合ってない」
p「なんか変えた?」
s「なにも」
h「あれ?サンプルあってたよね……」
s「あってた……」
p「とりあえず同じ結果だからsimulationかえてみよう」
h「入力は正しく読めてる? あとサンプルは問題と同じ?」

h「あ, 必要そうな式全部問題に書いてあったのか……」

いろいろやってるうちに残り時間が迫ってきていて焦りまくる.
となりの!#$%&()*+-./:;<=>?@[]^_`{|}~がK以外通していてやばい.
スタッフ呼んでリフレッシュルームに移動しはじめる.
スタッフがCongratulationsとか言っていてやばい(全完扱いなのか).

p「サンプルの答えのから逆算しよう」

h「すこし上を通ってる?」
s「あっそうじゃん」

280分 D AC

standingsを見るとbugrepのEがpendingで(凍結なのでpendingに見える)通っていると微妙なペナルティ勝負になりそう.
WF行くには学内1位は必須なのでやばい.
s「どれ解きます?」
h「H書いてる時間は明らかにないですね. Iに行くしか無いでしょう」
s「なにか思いついてますか」
s「最適な動きっていうのがまずわからないですよね」
s「とりあえず体力が少ないほうがpassを選ぶのはありえない?」
h「相手と自分の体力を減らすことに意味はある?ないならありえないけど」
h「あとはどんなときにpassを選びたいか?」

h「i番目でスコアjの時の体力の最大?」
s「そんな感じでやってみますか. 時間もないし」

h「bugrepの風船を見る限りEはまだ解けてないっぽい. katouも」
s「あと1問解けば勝ち確定なので通しましょう」

ラスト5秒, 一応それっぽい感じのコードが書き上がる.
サンプル通してる暇ないのでそのままsubmit.

直後にサンプル試すも全然違っていた.

300分 終了

なんかあったらしく5分間静かにしててねと言われる.

表彰式

あの会場WiMAX死ぬので本当に寝るしかやることがない感じだった.
8位のと2n賞をもらった. 眠気のピークだったのでそれ以外何も覚えていない

懇親会

いろいろな人と話した.
どうもWFに行くには来月のタイで頑張らないといけないっぽい.
あとは京大と筑波が台湾でスロットを取ってきてくれると日本のスロットが取れる可能性が出てくるらしいのでCJCとnekonyasoの方々に頑張ってと言いまくっていた.

みなさん, 来年は, Twitter ID とアイコンが書いてある名札を下げてきましょう!!!!

反省など

ちゃんとdiff(目でなく)取ったほうがいいかも.
ああいうsegtreeはバグの温床なのでライブラリ化したほうが良いのでは?との指摘を受けたので要検討(そもそも存在を認知していなかったとかはともかく).
解法を伝え聞いていたせいで先入観で他を潰していたことが後から分かったので対策を考える.

ねむくて後半適当になってきたのであとで書き直すかもしれません(たぶん面倒なので書き直しません).