とこはるのまとめ

多分考えたことがまとまっているはずです。きっと。おそらく。

2013アジア地区大会振り返り

おさけーさんによる別視点
http://www.osak.jp/diary/diary_201312.html#20131205

まとめ(1/8 追記)

binding.pryの一員としてICPCアジア地区大会の会津大会(日本大会)およびDanang大会(ベトナム大会)に参加してきた。

会津大会で国内大学としては、東大に次ぐ形となり、これが決め手となって世界大会(エカテリンブルク・ロシア)に行けることになった(まだ非公式だが)。Danang大会でもいい感じの順位まで来たがここでは次点止まりだった。

今回はFCCPC_alphaがかなり強いので半分は負けると考えていたが、その中で勝てたのは正直かなり幸運だったように思う。

チーム戦略としては、二人が実装主体で、一人(ぼく)が後ろでアルゴリズムなどを考えるというもの。
要するにこれの劣化版

劣化版というのは University of Agitsune より遥かに能力が低いということだが、今回はそれなりにうまく行ったように思う。あと、実際には二並列ではなくて、何回かやってみて我々のチームでは「メインコーダー」と「サブコーダー / デバッガー / 読解」みたいな分け方が妥当だなあと思った。書いてみたけど改めて後者が「何でも屋」って感じがする。すごい。

メリットは

  • 後ろの人は両メンバーと話し合いながらすすめることが多いので、時間的にどの問題からやるかとか、コーダー交代のタイミングを(それなりに)正しく制御できる。
  • 実装苦手な人が実装しなくてよい / 逆も。
    • ただし、実装量の見積もりはそれなりに正しく出来る必要があるので、本当の素人に任せるわけにはいかない感じがする

デメリットは

  • 後ろの人は実装する人に正しいアルゴリズムを正確な言葉で伝えなければならない
    • これは出来る人が全部一からやるよりも時間的ロスが大きい
    • また、間違った言葉で伝えてしまって大惨事になるリスクもある(Danang,C問題)

というところだと思う。

===================================================================
以下、大会中の流れ

注:以下は全くまとまってない
・もうだいぶ時間経ったので時系列が嘘っぱちかも。
・読み返していないので文章がおかしいかもしれない

会津大会


・すごいドキドキする
0完
・ドキドキしつつも事前の打ち合わせ通り自分はCを読む。
・ドキドキしているがまあこれは普通に座標圧縮でゴニョゴニョすれば大丈夫だと思う
・あとEを読んでおく
1完(A)
・領域の間に辺があるかどうかの判定がどうにもめんどくさそうだが、特に解決策も思いつかなかったのでそのままosa_kさんに投げる。
・その後、osa_kさんが領域の間を別の色で塗るというナイスな案を考える。すごいいけそう
・Eの概要も伝える。何も考えていなかったが、Dijkstraだと言われる。たしかに。
・Dを考える。何を考えればいいんだ…
・Gについてosa_kさんから3次元のマトリョシカだと言われたが、そういう系見たこと無いし、すぐに取っ掛かりが見つからないので絶対にヤバイ問題だと思う。
・思い違いかもしれないが、少なくとも3段階で最も簡単な難易度というのは大嘘だと感じてAを☓印で消す
2完(B)
・Dの詳細を詰めようとする。心臓バクバクする。なんだこれ。やばい。JOIですらこんなに緊張したか怪しい。
・C、 おさけーさんが失敗してるけど、みけきゃっとさんが行けそうと言っているので行けるかも。とりあえず任せてみる。
・D、 よく考えたら秒針を変数として(0<=x<60)としたら普通に式が立つじゃん。大体式立ちそう。
・Cがヤバイらしい。見てみると、たしかにみけきゃっとさんの方針はやばい。見落としだった。しくった。とりあえずおさけーさんに再び交代。
3完(C)
・D,Eどっちが早いか問われる。Eは20分でできるらしい。すごい。Dは式が完全ではないので、Eを任せる。
・Eをやってもらっている時間でちゃんと確認。これなら大丈夫そう
・みけきゃっとさんも分数を定義して行けそう、と言ってくれる
4完(E)
・みけきゃっとさんにDを任せる。
・そろそろドキドキが収まってくる。
・Hをosa_kさんがいい感じの幾何だと見破ってくれる。
・本質部分の話は昔きゅうりの問題で見たことがあると言ったが、僕自身完全に忘れていた。
・その問題は分割統治法で解いた覚えがあったが、今回はそれよりも制約がきついし、詳細忘れていたし、osa_kさんにメリットを説明することが出来なかったのでそれは実現せず(分割統治を使えば幾何のめんどい式を一切使わずに答えを求めることが出来る)
・osa_kさんが頑張ってHを詰めているうちにIを考える。わからん。
・Gもちょっと考えてみる。やっぱりやばい問題じゃないのという感想を持つ。
・Hの詰めの際に詳細の確認をされる。それっぽい証明を言って完全に方針が定まる。
・Dが少し詰まっているようにも見えたのでチラチラ見る。少し想定と違ったので少し指示を出しつつ、バグを直したら通る。
5完(D)
・Hの実装を開始。
・Iを考える。区間DPっぽいものを考えるがやっぱりわからん。
・みけきゃっとさんと新規問題の開拓をしようとするが、成果はない。
・そろそろ時間も押してくる時間だったので、osa_kさんのコードを見るようになる。
・なんかうまく行ってないっぽいのでみけきゃっとさんに印刷したコード投げると、すぐにヤバイ箇所を見つける。さすがデバッガだ。
・そこから何かあったか忘れたが、もう少し直したら通る。
6完(H)
・次に何を解くか。選択肢はF,G,I.どれもいうほど開拓できてない。実力不足感。
・おさけーさんの魔法の言葉「落ち着いて考えよう」
・ぼくはJを解くことを推奨しようとしていた(が、多分おさけーさんが完全に無理と判断しているので、どっちにしろ退けられていた)
・Gはやばいと主張し続けた。(これが正しかったかはわからん
・Iもきっとやばいと主張した
・その結果Fを考えてみた。
・Fでその前までわかっていたことといえば、「球面をうまいこと分割することだけど、球面とかうまいこと分割できるわけ無いじゃん」ぐらい。
・その辺を説明している辺りで、球面上での距離の大小関係は3次元の直線距離でも同様の大小関係を保つことに気づく。
・勢いのまま話して、それは蟻本にあることを言われ(もちろん僕も気づきつつ)開き、3次元をどうするかを考えて、それ以外の部分をまずはかき上げることにする。
・実装パートはおさけーさん、詳細の詰めはとこはる&みけきゃっと。
・まずは蟻本のアルゴリズムを思い出す。見たことはあったので、その辺は比較的楽。
・次に次元を上げた時にどうするか。いろいろ出たが、実装量的には、単純に2次元のときに枝刈?のようなことをそのまま流用するのが最善と判断。もしTLEならそのときに考える。
・ちょうどおさけーさんも書き終わったっぽいので、蟻本を見せつつ説明。理由も示しつつ説明したつもりだった(が、言われるがまま、という感じだったらしい。その辺難しい
・実装が終わる。なんかうまく行かない。
・以後はおさけーさんの日記通り。添字ミスが原因。
・最後の最後のSubmit。通った。安堵した。
7完(F)
・F問題のACに至るまでの過程が全員の力を使い切った感じがして非常にドラマチックだったのでかなり印象に残った

Danang 大会

会津とは対照的にわりと落ち着いた気分で大会に臨む。
世界大会ほぼ確実の状態だったからだろう。
0完
・問題文が1部しか配られないので、最初にホッチキスを外して、問題ごとに付箋を貼って最初に読む問題をそれぞれ渡す。
・Jを読む。どうみても行列累乗。でもSumのある形。一応メモに行列とその積を書いて確認。よさそう
1完(A)
・おさけーさんにJを渡す。これこれこうこう、という説明をする。やってもらっているうちに、Dを読む。
・Jがなんかおかしいらしい。色々見て、答えとしている行列の箇所が違うことを確認。サンプルがあったのを確認して提出するがWA.なんでや…
・印刷してもらって確認したりIやってもらったり、Cをちょっと考えたり。
・MOD 10^12じゃねえか!掛け算すると死ぬじゃねえか!!あほか!!
・なのでJを訂正。
・通る。
2完(J)
・Iもすぐ直すだけだったらしい
3完(I)
・Cの解法を伝える。
・O(NlogN)だったら通ると思い、1~Nで篩っぽい操作をする旨を伝えた(が、普通の篩の操作をしてしまっていた。篩なんて表現で伝えるべきではなかった。
・その間にFを考えるなどする。
・Fは0011100みたいなビット列で管理すると頭がおかしくなるので、0がa個あって、1がb個あって、みたいな記法で表現して考えることにする。0,1が逆でも問題変わらないので、(a,b,...)の列だけ考えればよいので、こっちのほうが楽である。
・Cがなんか合わないらしい。解釈を議論する。やはりよくわからん。色々試すけどダメっぽい。
・ので、Fを渡す。結局、縮約処理をシミュレートする感じにした。証明はできてない
・Fを実装してもらっている間にGの問題概要を聞いたりする。
・みけ「いくつかグラフが与えられて、それが同じグラフか判定する問題」とこ「へー、それって木だったりするん?」みけ「木だね」とこ「まじでwwwwww」
・つまるところ聞いたことある問題だったので、これは解けると確信するが、それは時間がある話であって、果たしてこれはうまく行くのか…
・Fのサンプルがそれっぽいので投げる。AC
4完(F)
・引き続き闇のCを考えてもらう。なんかみけきゃっとさんが気づいたらしいのでそれを元に検証が行われている。
・Bの問題も聞いておく。全域木の数え上げらしい。
・知ってた。正確に言えば、解けることを知ってた。詳細はあんま覚えてなかった。やばい。これは正念場だ…。
・思い出す。覚えている情報は次の通り。
+ 行列式が答え。
+ 隣接行列を使う。
+ Traceはなんか別に割り振る。
+ なんかマイナスを掛けるとか出てきたような気がする。
・いつか忘れたけど、いい感じにCもなんとか解けたらしい。
5完(C)
・それで、さっきの箇条書きを組み合わせてそれっぽい行列を作る。
具体的には、普通の隣接行列に対角部分に次数に-1かけたものを入れたもの。まあテストして正しいっぽい値でたし大丈夫でしょということでGOサインを出す。(計算ミスで正しい値が出ていた。これでGOサインを出したのは色々やばかった。
・投げている間にDを考える。なんか二部グラフっぽい。最小費用流で答えは出そうな感じはする。正当性はみけきゃっとさんに丸投げする。
・Bの行列式が0になるらしい。ほんとだ。たしかに計算しても0になる。
・もう一回さっきの行列式を思い出す。
・そういえば、さっきの行列の行列式を出しても常に0だったような気がしてきた。
・それだったら、確か一行一列抜かすんじゃないかなあ
・ということで、最後の行を抜かして行列式を求めてもらう。
・サンプルでそれっぽい値が出るが、+になったり-になったりするらしい。
・みけきゃっとさんから修正案も出るが、僕が「これは偶奇で場合分けだろう」と言う。
・結局偶奇がそれっぽい値が出るように見える。出してみる。AC
(結局、思い出した行列式はTrace部分は正で、それ以外の隣接行列の部分は-1を記入する、ということだったし、二重に間違って思い出していた)
6完(B)
・あと解ける問題は時間的にDのみ。
・最小費用流を実装してもらい、そして費用について逐一説明する。
・なんとか書き終わったが、時間がない。サンプルにも食わせず提出。WA。終戦。