JAG夏合宿2019に参加しました
(2019-10-04, imported from team-seadrive.com/blog)
夏休みを振り返る 第 3 弾です。
9/14-16 に行われた ACM-ICPC OB・OG の会(JAG)主催の強化夏合宿に Aobayama_dropout のメンバーとして参加しました。
1 日目
技術書典 7 の新刊の原稿が終わってなくてやべえ!! 深夜まで作業をやっていた結果若干寝坊。こたつがめにみどりの窓口に並んでおいてもらって切符を GET。なんとか乗車。
JAG の合宿は 2 年目。去年はオンサイト初めてだったが、この 1 年でたくさんイベントに参加したので今年は知り合いが多い。自己紹介で自分の同人誌の宣伝をしたりした。
コンテスト
今年は 1 日目に 5 時間セットが降ってきてひっくり返る。いつもの通りぼくが A 問題を読む。簡単なアドホックですがコーナーに殺されました(1WA)。AGC-A っぽかったかも。
B、C をそれぞれゆきのん、こたつがめが解いて 1 時間くらい。D をこたつがめが実装している間に E を読む。ゆきのんがシミュレートして正当性を検証する解をあげるが、制約で爆発。
ぼく「これアイテムの価値が$10^{10^5}$とかにならない？」
ゆきのん「うーん、多倍長整数！ｗ」
ぼく「は？」
あーだこーだ話していると mod を取れば大丈夫そうという話になる。実装を見守る。
割り算で逆元を取っていなかったりすることを指摘して投げる。WA！なんでぇ～ こたつがめも D が通らずつらそう。
ここで順位表を見ると J が通っているっぽい。実験をやると x,y 座標ともに共有しない集合に分けるみたいな解法が降ってくる。えーどうやんのって言っていたらこたつがめが 2 部マッチングを使うことを教えてくれた。書いて AC。
D がオーバーフローで落ちているっぽいと言ってこたつがめが Python で書き直したら通ってキレていた。かわいそう。
全員で E のバグとりをやる。mod の衝突っぽそうなので複数取ってみる。いくら取っても通らない。えー 7 個取って衝突するとかある?他がバグってそう。
……と思っていたらなんと||と&&を間違えていたことが判明。あ ほ く さ
結果 ABCDEJ の 6 完。
夜
部屋は pazzle さん、ぴーよさん、Sen さんと一緒だった。
原稿ちょっとやって布団に刺さってた気がする。懇親を捨てた男。
2 日目
朝
朝食に行くかと同室のみんなと話をする。歯を磨いて部屋に戻ったら誰もいなくなっていてひっくり返った(2 回目)。
なんか顔洗って部屋戻ったら人々消滅してて一人で食堂に向かっている
先に行ったと思われていたらしい。すまん。
コンテスト
問題難易度全シャッフルは初めてで戸惑う。しょうがないので流し読みしていると、D がビット全探索っぽいので考察をすすめる。
E をこたつがめが通した後に書くと TLE る。怪しいところを直してもらって AC。
A が通り、他を読むが難しい。I の実装と提出を見守っていると WA。つらそう。
J の考察をゆきのんと進めると、$O(S)$で計算できる式($1$から$S$までの$n$乗交代和)が生えるが、$S \leq 10^9$なので終了。オーダーを落とせなかった。
I のほうはジャッジが間違っていたらしく通っていた。ADEI の 4 完。
J はベルヌーイ数というものを使ったり、ラグランジュ補間によって計算できるらしい。うーむ。
夜
ABC に出る。
ん、懇親してABC出ようとするとお風呂入れなくて破滅するのか
@AokabiC 全完すれば入れますよ
E の文字列問題が解けず冷え散らかす。線形アルゴリズムをいじる着想がでて解けないのは本当にダメ。
原稿やって寝る。
3 日目
朝
朝食、nullしか置いてなくて泣いちゃった
みんなで朝食に行けたが、null しか残っておらず涙……。
コンテスト
4 時間北大セット。
A 問題を読む。簡単すぎて怪しい、"Arbitrary"という単語の解釈に不安があり、全員に聞くが**全員わからない**。えぇ……
2WA です。ペナしか生やしてなくてすいません。
B, C がサクッと通るが、あと解けそうな問題がなくてキツイ。冷え散らかしそうだったが、こたつがめが E の DP 遷移を生やして終了 8 分前に通した。
早解きが効いて 4 完最速。ここまでなにもできなかったのは久々でつらい。
終了後
自分の進捗がやばかったこともあってまっすぐ東京駅に向かった。ゲーセンはまた今度……(JSC でやりました)
https://scrapbox.io/files/624092a749094c00201bffe0.jpg
東京駅・六厘舎。うまかった。
こたつがめがコンテスト中に詠唱したもの一覧
・スーモ
・ゆうさく
・だいちくん
・水素の音
・変態糞土方
・「邪淫」について
なにこれ?