読者です 読者をやめる 読者になる 読者になる

ゆらのふなびと

競プロ, Python, C++

会津大学競技プログラミング合宿2016 参加記

参加記 会津合宿

経緯

もともと行く予定ではなかったが、JAG夏合宿に参加したら会津にも行きたくなってしまった。なので行った。

0日目

高速バスの値段の都合で、木曜発の夜行バスで金曜に東京入りしていた。山手のゆきラーメンがとてもおいしかった……!(また行きたい)

マヨマヨとのアキバでくまみこを探そう大作戦は敗北に終わる(なぜか全然見つからなかった)

1日目:立命館セット

高速バスを乗り過ごした。次取れた便が4時間後だったので、この日の目標は「コンテスト終了までに会場に着く」になった。コンテストには車内からオンラインで出ることに。

~コンテスト~

http://judge.u-aizu.ac.jp/onlinejudge/contest_standing.jsp?id=ACPC2016Day1

Bを読む。Nが小さいので整数比の全探索ができそう。WA。落ちるケースがわからん。WA。いろいろ試していたらif文の判定を間違えていることに気づく。AC。

izryt氏がAを通す。プロ。

kenkoooo氏にCを任せて(つらそうだった)、順位表的に望みのありそうなEへ。最初はなんじゃこのわけわからんリアクティブは~(しかも確率的に情報が欠落するとは)という感じだったけど、冷静になると次数しか要らないのでlstクエリn回聞いてハイ!wという感じだった。ここでバスが会津若松駅に着いたのでizryt氏に実装を投げる。AC。

終了30分前に現地に着くも研究棟に入れずうろうろしていると、やざてんさんが助けに来てくれる。が、入れない。学生証的なアレが必要らしい。中から見かねた会津大生(競プロ勢ではない)が開けてくれる。ヅ大生優しい。

kenkooooさんにCの概要を聞くとフローらしい。フローの流れた辺の列挙がうまくいっていないらしく2人でずっとデバッグしていた。終わり。

~~~~~~~

コンテスト終了後はkenkoooo氏、ctyl氏、tookunn氏と駅前のhoge屋でご飯を食べた(しおチャーハン割とおいしかった)。会津の名物を知らず。

会津合宿への参加を決めたのが合宿2週間前くらいだったので近くのホテルが取れず、会津若松駅から5駅ほど離れたところにあるユースホステル的なものにctyl氏, tookunn氏と泊まることにしていた。想像以上に限界集落だった。

この日はこどふぉがあったので宿の談話室をお借りして即席オンサイトをやっていた。

2日目:会津大セット

Twitterでチームメンバーを募集していたらDarseinさんに誘っていただけたのでご一緒することに(全く想定していなかったのでびびった)

同じくメンバーを探していたry0uさんをお招きしチームsoujirou結成。

Dさんが司令塔的なポジションで、僕とry0uさんがコーダー的な役割で行こうという話をしていた。

~コンテスト~

http://judge.u-aizu.ac.jp/onlinejudge/contest_standing.jsp?id=ACPC2016Day2

Bを読む。N, Kが小さいのでN_C_Kを全列挙。各パターンについてはaの大きい方から貪欲に割り当てる。Aをry0uさんがAC。DさんがDのFAを狙って書いていたのでその間に紙コーディング。Dがムズいとのことなので交代してBを書く。あれ、サンプルが合わない、けどそれは余った芋を足してないからだ。AC。

Eを読む。頂点数nかつ直径dの無向グラフでありうる最大の辺数を答える問題(多重辺、自己ループはなし)。制約がn<=109とでかいので一般式を求める問題だろうと推察。n=4,5を描いてみると、

  • d = n - 1 (max) のときはパス, d = 1 (min) のときは完全グラフ
  • d >= 2 のとき、辺が最大になるのは、パスの状態で距離d以上なる頂点間すべてに辺を張り、距離dの辺を1つ除いたグラフ

ということがわかった。計算していたらO(1)で行ける式が生えた。AC! このとき順位表で一瞬2位(antaさんのすぐ下)になっていて最高の気分だった。

以降はDさんから飛んできた解法を実装するという流れに。Gの話を聞くと確かに簡単な幾何でいけそうという気分になったので、書く。バグらせる。Dさんに見てもらうと、こっちの方が簡単そう~というアイデアがいくつか出たのでそちらに鞍替えする。バグらせる。なんでや~と思っていたら交点を求めるために取る線分の位置が間違っていた。直す。AC。Dさんと話す度にコードが短くなっていくので面白かった。

次はH。DP。同じ場所で次に取れるのが15分後、辺のコスト>=5分ということを考えると、a->b->c(c!=a)の遷移はいつでもボールを取れるので取る。a->b->aの場合は2 * cost(e_ab)>=15ならボールを取れる、そうでなければ待機するとボールを取れる。状態を(直前に使った辺, その向き)としてDPを書くがサンプルが合わない。なんでだろう…とDさんと一緒に出力とにらめっこしていると、a->b->aのときに待機しない遷移がないことに気づく。これが終了20秒前くらいのことだったので、時間切れ。

~~~~~~~

チームとしては7完8位で、オンサイト1位だった。解説を聞いていたら5個くらいオンサイトFAが取れていてびっくりした。

FとIが面白かった(というか会津セットは全部面白くてすごい)

終了後は懇親会。競プロerがなんでも競プロに結び付けていて面白かった(注文のキュー、座席のマッチングなど)。kenkooooさんが数々の名言を残していた。

3日目:北大セット

この日は天下一プログラマー船見結衣として参加しました。

~コンテスト~

Bを読む。スタートとゴールを決めて全探索するんだと最初は思った(N<=1000だったからというのもある)。桐間さんがAを書いている間にサンプルを見ながらアイデアを詰める。p_i - d > 0 のところでだけ降りればいいっぽい。桐間さんがAをACしたので書く。が、p_i - d の和を毎回求めていると自分の解法では O(N3) になることに気づいたのでいったん涼風さんにパス。先に和をとっておけばいいだけなんだけどなぜかやたらつまっていた。詰めたので書く。書いてる途中でスタートのforループいらないじゃんと思って消す。サンプルが合ったので投げる。AC。(よく考えるとゴールのループもいらなかった)

涼風さんがCを、桐間さんがDを解いていたので、E以降を一通り読む。Eは確率のDP、Fはフローということはわかるけどどうやるんだろうという感じ。Gは幾何ということしかわからない。Cがバグっていたのでデバッグを手伝う。役に立てなさそうなのでお菓子を食べていたらC, Dが通った。

次はGがよさそうという話になり3人で考える。凸包を考えるといいらしい(言われてみればそれはそう)。凸包の辺のうちどれを長方形の1辺に合わせるかを全探索するとよさそうという案が出る。それは本当か?というツッコミを入れしばらく反例を探していたが本当だったのでsorry

矩形の面積を求めるために選んだ辺からの最遠点を取る必要があるが、N<=105なのでうまくやらないとTLEしそうという話に。桐間さんによればキャリパーしながら三分探索で行けるらしい。キャリパーis?状態だったので蟻本を読んだりお菓子を食べたりしていた。

ヘロンの公式が必要だったらしく、どんなんでしたっけ?と確認されたらなぜか覚えていたので我ながら引いた。

Gは結局サンプルが合わず、時間切れ。終了後怒髪さんに、実は凸包の頂点数はそんなに大きくならないので最遠点は線形探索でいけるという話を聞いて、天才か~~という感じだった。

~~~~~~~

解説を聞いていたらE, Fが面白かった。Eは手持ちのカードを陽に持たなくても各パターンのものが何個あるかを持っておけばよいというのが頭いい(ループが発生しないのもすごい)。Fは「ボトルネックになるところだけ調べればよさそうだな~」という気分になっていたが解説を聞いて「ボトルネックってカットやんけ!」という気持ちになった。フロー慣れてないので、解きます。

感想

会津合宿、楽しかったです。ここに書いたほかにも他にも限界集落の思い出とかいろいろあるんですが、それについてはctylさんとtookunnさんが詳しく書いてくれるでしょう(丸投げ)。

ホスト校である会津大のみなさん、作問陣の北大、立命館のみなさん、お疲れ様でした。チームを組んでくれた方々もありがとうございました。

会津はじっくり観光したいので、また行きます。来年も合宿があればぜひ行きたいです。

参加者のみなさん、こどふぇすでまた会いましょう!!