今度はコンテストの方です．コンテスト以外は→The 2015 ACM-ICPC Asia Daejeon Regional Contest 参加記(コンテスト以外) - kyuridenamidaのチラ裏
毎回敬称が消えるのでまーすさんとustimawさんについては開き直って敬称略とします．敬称は心のなかで付いています．心のなかで．
タイムスタンプから記憶復元してるんで，結構細かい時系列バグってるかも．
コンテスト前
- 日本語キーボードが使えるかどうかだけがめっちゃ心配だった．
- 10時から開始となっていたけど，少しだけ開場が遅れている．
- 大丈夫かなあと思ったけどちゃんと始まった．
[00:00]コンテスト開始
- 開始後ただちに僕がキーボードを繋ぐ．
- 開始後，まーすがVSの設定をする ∧ キーボードの設定を行うことにする．
- ちゃんとキーボード日本語で使えてるっぽい．
- コンテスト問題1部しかない...千切る．僕はA,B,C,Dを読む．ustimawがI,J,K,Lを読む．
- Aはフローっぽい，Bは物理っぽくてエグそう，Cはめっちゃフローっぽい，Dは読めない
- AとかCの題意をまーすに説明したりする．少なくともCはフローですねとなる．
- 少しして一部の問題の読解が終わる．ustimawがJ解ける?と言う．
- J問題の題意は「整数K(7≦K≦1000)を3つの素数の和で表せるなら具体的な構成を1つ，そうでないなら0を出力する」
- (これは弱いゴールドバッハ予想不可避ですね...(しかも最近CF Div2で出た))
- まーす「余裕やで」
- まーすがパパッと実装して，きちんといくつかのテストケースを手元で試す．少々バグるがVSの力でデバッグが30秒くらいで終了．それでも割と慎重に試す．
[00:19]J AC
- 僕がA考えてたらustimawが「L簡単そうやし読解してくれん?」と言う．
- 順位表を見ると既に3完してるチームがいる...やばいやばい．
- とりあえずustimawがIにとりかかる．Iは株を売買する問題．
- サンプル合ったので出してもらう
[00:28]I AC
- Eの解法は詰まっているらしいのでEはまーすが書く．
- Lは本当に記述量の短いやるだけだったので，僕はL誤読してないか再確認して，具体的にどうタイピングするかを完全にイメージする．
- まーす「サンプル合ったので出してみる」
[00:33]E AC
- 当然結果が返ってくる前にバトンタッチ，僕はLを書く．書いてる途中にEがACしてることが分かる．
- 実装が終わる．手元でサンプルが通る．とりあえずPC^2でも通ることを確認．
[00:36]L AC
- よしよし4完．11位くらい．でも全員4完で止まっている…．
- Cとかがフローっぽいのに上位チームが4完で止まっているのは不思議な感じがする．ライブラリ貼れないからかなあ．
- まーすにフローだね，と承認を受けたのでとりあえず僕は最大流のライブラリを写す．
- 僕がライブラリ写してる間にまーすが「HはFaulhaber's Triangleそのままで数論ライブラリに有るから貼るだけ」と言い出す．
- ustimaw＆ぼく「！？」
- まーす「入れてて良かった数論．まさか役に立つとは．」
- フローを写した後，Cがグリッドグラフだから二部マッチング的なフローというのは分かるのだけれど，辺を何回も使えるし，いまいちどう辺張ればうまくいくのかただちに思いつかなかったので実装をまーすに任せる．
- その間に写経したソースを印刷して間違い探しを行う．いくつか見つかる．
- とりあえずサンプルが一致．提出する．
[00:54]C AC
- 2位になる．
- とりあえずまーすがHのライブラリ写経する．
- その間Aの解法について話す．
- ustimaw「A，最小費用流で行けないかなあ」
- ぼく「交差するケースないかなあ...あーーーいや無いか..なさそう．それで上手くいきそう？」
- ustimaw「Kなんですが，木の編集距離って一般的な概念ですかね？知ってますか？」
- まーすとぼく「知らないなあ...」
- まーす「サンプルが1あわへんねんけど手計算を...いやこれは俺がやったほうがいいか」
- (数分後)まーす「あっ，これ総和がk=0からだ．ライブラリと少し違う．」
- サンプル一致した．出します．
- ジャッジ待っている間慶應にタイムペナルティで負けていることに気づく．やばいなあ．
[01:18]H AC
- 6完きたー！！1位だうおお！！
- ぼく「ナイス！！(大声)」
- まーす「うるせえぞ騒ぎすぎ」
- ぼく「すまぬ」
- 僕たち「話し合ったんですけどA問題，WFして最小費用流で行けそうじゃないですか」
- まーす「いけると思う」
- ぼく「WFのO(n^3)，この制約で最悪ケースが大量に来たらTLEするかもですけど定数倍軽いし韓国大会だし大丈夫ですよね..?そもそも最小費用流でもそれくらいかかりそうだし..(ただ二部グラフの最小費用流なので最悪ケースを達成しそうにもないなとは思っていた)」
- まあ大丈夫だと判断して最小費用流を写す．10分くらいして写経が終わる．
- ぼく「あの，フローのグラフ，構築するの苦手なんですけど」
- まーすたち「え～」
- ぼく「これワーシャルフロイドして二部グラフにしたらいいんですよね．ソースから左に繋いで，右からターミナルに繋いで，真ん中はそのワーシャルフロイドグラフで...誰かやりませんか？」
- まーすたち「せやで．自分でやりゃええやん」
- ぼく「やります．ライブラリチェックustimawさんお願いします」
- ustimaw「こことここが間違ってますね」
- ワーシャルフロイド書いて黒い頂点対にだけ辺を貼る．
- バグる．まーすにデバッグバトンタッチ(なぜなら彼はVisualStudioマスターだから)
- ステップ実行してたら配列のインデックスがバグっていることに気づく．修正してみる．サンプルが合う．
- 出してみる．TLEしたらワーシャルフロイドの部分を幅優先探索に書き直そうとか思う．
- 自分の担当分だし，通って欲しくてめっちゃ祈る．
[01:40] A AC
- よっしゃー！！！首位維持！まーすのHのアドバンテージがかなり利いている．
- ここから解法が判明しているやつが少し怪しくなってくる．
- Fはみんな考えたけどいまいち上手く行く確証がないし上位校でさえWAしてるチームが多すぎてかなり危険問題と判断していた．
- ustimawと息抜きに別の問題考えてみない？と考える問題を入れ替えたりしてみる．
- Dは誤読の可能性があってまだだらだら読んでいた．
- ustimawとBは連立方程式系だけどサイズがでかすぎるから反復法等の近似計算で成り立つ系じゃない？みたいな話をする．ただし連立方程式が本当に収束するかどうかは分からない．
- Kは僕らはさっぱりだったが，まーす曰く「O(n^3)っぽいんやけど書いてみたら速い系かも，それしか思いつかんのよね」
- まーす「とりあえずそれでいこう．詰めとくからきゅうり入力を木に直す部分書いてくれる？」
- ぼく「はい」
- とりあえず書けたらまーすにバトンタッチ．
- まーすがKを書いている間Dとかを考えたりしてみる．ustimawの仮説に意見を求められたりするけどいまいちピンと来ない．苦手なタイプの問題だなあ．Fについても，お互いにFを考えたときに得られた知見を共有してみるが進展無し．
- Gは僕は問題概要を聞いただけでノータッチ．「なんか無駄な角を取り除く感じで，嬉しい列を持つテクみたいなやつでは？」みたいな適当な提言だけして終わる．
- Kが書き上がったみたいで，まーすがKをVisualStudioの力でパパッとデバッグしている...
- サンプルが一致したらしい．出してみる．
[02:22]K AC
- まーすのテンションが上がってくる．
- うおおおすごい！！！
- 解ける問題もうなくなってきたなあ...残るはB,D,F,G
- まーすがG問題分かったけどこれ実装重いなあ...と言う．1時間くらいあれば通せるかも...と言っている．
- まーすにGの実装を任せる．
- 横から見てて境界とかがめっちゃ面倒くさそう...頑張れまーす．
- まーす「あれ，G問題これベースセグメントってx軸通らへんの？」
- ustimaw「そうとは限らないっぽいよ．サンプルがこんな感じっぽいよ(図示)」
- 実装量が多い分僕は無駄に不安になり，ちょいちょいまーすさんが「こんがらがってきた...」とか「誤読してた...」とか言う度に「破綻とかはしてへん？」「解法は確信あるん？」とかクソリプを飛ばすマンになっていた．
- まーすが「いや破綻とかはしてないよ．実装仕切ったら絶対通ると思う．」と言ってくれて安心する．
- とりあえず昼食とりつつ僕はB問題についてどういう性質があるか考える．ていうか勘違いを防ぐためにBの入力部分が具体的にどうなっているのかをちゃんと頭に叩き込む．インデックスに負の値が発生してたりしてビビる(物体のidか固定点のidかを区別するためにそういう入力らしいｗ)
- 「Bの連立方程式を成分毎に考えるのしんどいしなんか√とか出てきて一次連立方程式じゃないやん～～」とかよくわからんこと言っていたらustimawが「ベクトル使えへんかなあ」と言ってくれて電流が走る．当たり前のことになぜ気付かなかったんだ．少し怖かったので実際に成り立つことを確認．
- 実際にBのサンプルの行列書いたりしてみる．手書きの行列の上では固定点の座標を定数として扱っていてやや絶望感が漂う．
- 「Bはやってみなきゃ分からない系」だと主張しまくる
- Bを反復法(加速するやつ)でやるとして，収束速くするにはどういう嘘改善をすると良いかみたいな話をustimawさんとする．
- Bの改善案として出たのは，固定点から芋づる式に位置の変化が伝搬するようにソートしておくとか，初期値をうまく決めるとか...．
- まーすがGを書き上げたっぽく，Gのデバッグをしている．手計算結果とステップ実行における変数の値を逐一確認しながら手際よくデバッグしている．すごい．
- サンプルが一致したらしい．
- まーす「まあサンプルは合ったんだけどうーん...」
- かなり実装量が多そうだなあ．出してみるしかないので出す．
- まーす「トイレ行きたいけど結果見てからじゃないとトイレ行けねえよ～～」
[03:41]G AC
- チーム内でめっちゃ湧く．
- まーす「よっしゃあああ！！！！！！」
- チーム「うおおお」
- まーすのテンションが最骨頂に達している．いつも冷静なustimawさんも珍しくめっちゃテンション高い．
- ぼく「テンション高ない？ｗ」
- まーす「テンション上がらざるを得ないでしょこれは...疲れたからあとは任せたゾイ」
- これスロットほぼ確定では，今までWA0でペナルティでは負けないしみたいな話をする．
- ustimaw「まあ油断はしないほうがいいよね」
- とりあえず残り何やるかというと，Bが一番簡単そうに見えるので，半分ダメ元で書いてみる．なんか制約多いし，物理的な題材だし，勝手に嬉しい性質成り立ってくれやと願う．
- なんかみんなトイレ行ったり食べ物取りに行ったりしていて気づいたら僕一人が席に座っていたりする．
[04:00]順位表凍結
- 同完数で2位のKAISTがFに提出した結果が返ってくる前にstandingsが凍結される．
- Bで，固定点を変数として置いたりしたほうが実装が楽だということに気づいて置いたりしつつ，とりあえずソースを書き上げる．
- なんか普通にセグフォる．まーすにデバッグしてもらう．
- 入力ミスだった．それでも答えが合わない．うーん実は連立方程式が間違ってんのかなあ...
- サンプルが実は合わないからみんなだしてないだけでは...???
- いや，連立方程式にサンプルの答えを入れたら連立方程式が正しくないということはなさそうということが分かる．
- よくみると反復法の式を間違っていた--;
- それを修正したらサンプルが合う．
- ってことは，みんな敬遠してるだけか(確信)
- あとは完答数の戦いになると思うから，WAいくら出してもええんちゃうかみたいな話になる．
- とりあえず変数N≦1100としてO(N^2*反復回数)の反復法を反復回数を100にして出してみる．
- 一回の反復における変更幅の最大値がε以下になったら打ち切りみたいな条件にもしたかったけど，とりあえずどれくらいループが回ったらTLEするのか気になるのでそれはしない．
[04:21] B Wrong Answer
- あ，TLEではないんだ．まあWAですよねえ．
- ustimaw「芋づる改善入れてへんのか．容易に反復時間かかりそうなケースが作れるんだから入れたほうがよさそうじゃない？」
- きゅうり「どうしようかなあ．実装だるいなあ．」
- まーす「まあ面倒くさいならお手軽改善からはじめない？」
- まーす「行列は疎？疎なんやったらうまくデータ構造持てばよくない？ていうか疎なんやったら本質的に反復法のオーダー改善せえへんか？」
- とりあえず疎行列を持つデータ構造にしてみる(普通に非ゼロ要素だけ持つだけ)．
- オーダー改善してる気分だったので1000回反復にして出してみる．
[04:33] B TLE
- チーム「あれ，1000倍速くなったと思ったんだけどなあ．うーん．ちょっと変えてみるか．」
- 反復回数300にしてみる
[04:34] B TLE
- あれれ...100回にしてみる．
[04:36] B WA
- 200回にしてみる．
[04:37] B WA
- よく覚えてないけど適当な改善してみる
[04:38] B WA
- やっぱ収束してないっぽい...?
- 適当に全ての物体の初期点を重心に置いてみる．
- まーす「定数倍改善は任せろ～～」
- まーすがvectorとかをうまく減らして定数倍改善を試みる．
- ぼく「全部のケースで何百回も回す必要はないし，TLEしなかったら収束してることがわかるし，epsによる判定がいいと思うなあ」
- epsをサンプルが通るくらいの適当な値にしてみる．
- なんか色々やったなあと思いつつ提出．
[04:43] B WA
- あ，収束を誤判定してるっぽいな？
- もう少し適当に弄る．
- 出してみる．
[04:46] B WA
- まだ収束を誤判定してるっぽいなあ．
- さらにもう少し適当に弄る．
- とりあえずダメ元で出したので，芋づる式実装しようかなあという話になる．
[04:47] B AC
- まーす＆きゅうり＆ustimaw「！？！？？！！？！？！？！？！！！！！！！！！！！！！」
- ｷﾀ─ｗﾍ√ﾚｖ～(ﾟ∀ﾟ)─ｗﾍ√ﾚｖ～─!!!!
- チームがめっちゃ湧く
- 残りの時間はもうどうしようもないので，順位表を見て，最悪ケースで自分たちがどうなるかの見積もりを行う．
- このチームにはペナルティで勝てるだとか，SNUのCompCertが提出しているものを全て通していたらヤバイだとか，そんな感じのことを話す．
- ひたすら祈る．
[05:00] コンテスト終了
- あとは祈り
感想
- 9完で油断してたけれど，結果として10完が結構多かったので，B通してなかったらかなりやばかった説がある(それでも3番手なのでいくらかスロットがもらえたかもしれないけれど，割り当てられてるスロットが2.2とかだと1.0ずつ消費されて多分かなり厳しかった．
- 韓国で色んな運を使い果たした気がする．
- まーすライブラリヤバイ
- ていうかチームメイトの一発AC力ヤバイ
- ustimawさんのベクトルで考えようぜの一言がなければ多分B解けてなかった．
- 割とチーム練習とかあんまりしてなくて日常的に会ってないと，お互いがお互いに遠慮して声かけづらくなるんだけど，チーム練習とかのおかげで気軽に何かしら指摘できるようになっていたのは大きかったかもしれない．
- 特に息抜きに問題交換しようと言ってくれたおかげで色んな問題を読んで考えることができた．個人でコンテストに参加してると絶対こういうことはできないのでうまく働いた気がする．
- 途中まででもここまで1位をキープできたのはチームで初めてだと思うし，今までの練習よりも遥かに良いパフォーマンスを出せた気がする．それは問題の相性が良かったからなのかstandingsがあったからなのかはまだ分かんないなあという感じ．いや，多分まーすがVS使えたからだと思う．多分そう．
- B，0WAは無理だけど少なくとも5WAくらいには抑えれたんじゃないか説はある（ただたくさん投げて完答数が増やせたら嬉しいという状況だったし，後からなら何とでも言えちゃいますね）
