JAG夏合宿2018 参加記 - すいバカ日誌

はじめに

JAG夏合宿2018の参加記です。

今年が初参加だったのですが、結構濃密な3日間だったので参加してよかったです。

3日間とも、ICPCのときのチーム Zerokan_Sunshine (@nakano, @kazuma, @suibaka) で出ました。

Day1

当日会場まで

原宿からオリセンまでが意外と遠く、その上雨が降っていたので大変だった。
代々木公園からオリセンは目の前に見えるのに、通路が見つからなくてめっちゃ迂回したのだけ覚えてる。

コンテスト

台湾の国内予選2017の問題を使っていたらしい。

僕は ABDEF を実装。

各問題の流れを以下に書く（Day1 に関しては書かなくていい気がするけど）。

A問題
- 書いてあることを書けば通ります
B問題
- 10年以上前のPCKみたいな問題だった。full house を hull house とタイポして1WA。
C問題
- 僕は読んでない。kazuma が通してたかも？誤読して難しい問題解いてたとか聞いた気がする。
D問題
- 実装ゲー。今見ている位置の前と後ろを 2 つの deque で管理していい感じに実装した。
E問題
- 基本的な解法は瞬で、コーナーケースを忘れてて 1WA。これは割とすぐ気づけて（nakano が見つけてくれて）直した。
F問題
- 他の問題を解いている間に nakano が実験して式を生成していた。なのでそのまま書いた。実装ミスって1回REしたけどすぐ気づいて修正（サンプルが弱かったので気づかなかった）。
G問題
- どう見ても kazuma が得意なので丸投げ。投げたけど通らなかった。残念。
H問題
- 解けなかった。パット見どっちにしろ実装大変そうだな～と思って考察もあまりしていなかった。

コンテスト後

生活リズムが崩壊していたところを徹夜で無理やり戻したため、20時ぐらいに睡魔が襲う。

そのまま寝落ちしてAGC寝ぶっち。

同じ部屋の人に聞いたところBが激しかったらしい。~~でなくてよかったね~~

Day2

コンテスト

Gifted Infants の3人（yosupo, sigma, maroon, 敬称略）のセット。ヤバイ問題がちらほらという感じだった。

僕は ACFH の実装を担当。この日は僕が戦犯と化していた。

A問題
- 中国剰余定理いきなり出すのかとビビる
- 冷静に考えると 17 * 107 通りしか無いのでやるだけだった
B問題
- 知らないけど気がついたら kazuma が通してた
C問題
- 基本方針はすぐ出て書いたけどサンプルが合わねえ
- よく考えたら約数を列挙した後にさらにそれを分割できることに nakano が気がつく
- 直して修正。WA。
- 偶奇の扱いが雑すぎた（というか修正しているうちに間違えて消していた）のが原因だった。直してAC
- この問題でぐだってるあたりが僕のチームの弱いところ
D問題
- 何もわからないから後回しにしていたらコンテストが終わっていた
E問題
- 問題読解して kazuma に投げてみる
- 伝達ミスがあってロスが発生。kazuma ごめん
- 僕が違う問題やってるうちにいつの間にか FFT に落ちていて AC
- 1WA 生えてたけど理由は忘れた
F問題
- やるだけじゃん（笑）とかいって実装
- サンプル2が合わない
- 間違ったコードを埋め込んでサンプルが通ったと勘違い（サンプル 2 が偶然あってしまって、サンプル1 が代わりに落ちていた）
- 気づかず投げて WA
- サンプル2をよく眺めると、誤差爆発を狙ってそう
- 不可能
- kazuma神「これ mod で有理数いい感じにやるやつでは？ｗ」
- 当然ライブラリがないので、その場で適当に生成した（実装量がエグいことになった）
- if の条件節でトートロジー（s == s みたいなの）を間違えて書いてしまい 1WA が生える
- 直してAC。これ通ったのは割と嬉しい
G問題
- 嘘が生えては一瞬で嘘が判明するみたいなのを5分ぐらいやる
- 無理なので、無理です（は？）
H問題
- なぜか kazuma に丸投げされた
- KMP すればやるだけというのはすぐわかった
- 何故かサンプルが合わない
- 最初に文字列を reverse していて（意味不明）、消し忘れていた。合うわけ無いだろアホか？
- 直して AC
- reverse に何故か全く気が付かなくて1時間ぐらい溶けた
  - もしかしてKMPじゃなくて Zalgo だったっけ？とか、あまりにも通らないから SA で頑張って書くかとかいろいろ考えてしまった
I問題
- ドン引き
- kazuma が解けないなら無理という感じで撤退
J問題
- kazuma と nakano がやってた
- サンプルは合うけど全然通らなくてつらそうだった
- 解説を聞いた後にどうだったか聞いたら、普通に考察ができてなかったらしい
K問題
- なんか場合分けしたら 2 パターンぐらいになるなあ
- 小さい部分問題になるケースと、そうでないケースの2パターン
- そこからすすまないので撤退、多分考えても解けなかったと思う

コンテスト後

この日は opencup もあったので参加。
opencup 終わってから気がついたけど、解いた問題のすべてを僕が実装していた。
流石に今日は実装しすぎて（一日10時間もコンテストやってるの異常では？）疲れたので、布団に入ったらすぐ寝てしまった。

Day3

今日は JAG の問題セット。典型が多くて僕は楽しめた。

僕は ACGJ の実装を担当。通らなかったけど E とかも書いてた。

A問題
- よくわからないけど投げたら通った。こういうのが一番怖い
B問題
- kazuma 誤読。WA が来て nakano に誤読を指摘されていた
- 難なくAC
C問題
- nakano に概要聞くとやるだけだった
- AC
D問題
- 最初あんまり誰も考えてなかったので僕がちょっと考える
- kazuma のほうが得意そうだなあ
- Trie でいい感じにやっても解けそう、実装は気をつけないと文字列長がでかいのでメモリが危ない？
- どっちにしろ僕が書くより kazuma が書いたほうがパフォーマンス高そう
- kazuma に投げると普通に二分探索して2つの範囲求めてやればよくない？となる
- それはそう
- 選択肢はいろいろ (Wavelet Matrix でもいいけど写経がめんどくさい）あったけど Merge Segment Tree で通していた
E問題
- やるだけやんけ（笑）となり書く
- T L E
- Day2 の再来か？となるが冷静に考えると普通に O(N^2) ですありがとうとなる
- ベクトル（直線）に分けて Convex Hull Trick みたいにやるんじゃないの、という話を適当にする
- なんかこのタイミングでは反応がいまいちだった（というか、どっちにしろ実装が非常に重い）ので保留
  - 終わり際に CHT の話をしたらそれで解けるじゃん、みたいな空気に。結果的には取り組まなくても良かったけど、ちょっと危ないムーブだった気がする
- 定数倍改善を考えるがまあ通らないので諦め
F問題
- ゲームだし、僕よりは kazuma か nakano のほうがいいので kazuma になげた
- kazuma は K を書くことになったので nakano が F を考える
- めっちゃ実験してたように見える
- 他のチームに比べかなり遅いけどAC。通ればなんでもええんや
G問題
- パット見難しそうなので後回しにした気がする
- あとになって戻ってくると DP を前からやるだけで解けるねとなる
- 書くまでもなく実装が面倒、これぞICPCだなあ
- ややこしいパートを前計算しておいてデバッグしやすいようにした
- サンプルが合うので投げる、WA
- 前計算パートがちょっとだけバグってた（先頭を 0 or 1 のどちらにするかの場合分けが甘かった）のを nakano が見つけてくれた
- 直して AC
- これもかなり時間がかかっていて、大反省
H問題
- どう見ても LP なので双対を取ってから最短経路かフローでしょ
- 最悪シンプレックス法とか（かける人がいないので棄却）
- 双対を取ってから詳しい人がいません、終了です
I問題
- しらないけど kazuma が通してた
J問題
- nakano が読んでいたので教えてもらう
- 奇数長で行けるなら +2k で素数は作れるからという話を聞く
- すると遇奇でわけて BFS やるだけなので適当に書いてAC
K問題
- kazuma と nakano がやってたから関わってない
- あとで聞いたら超典型っぽい。通ったときはあまり解かれてなかったので意外だった