JAG夏合宿体験記

概略

競技プログラミングには、ICPCというチーム戦の大会があります。7月にあるその国内予選を勝ち抜くと例年11月~12月にあるアジア地区大会に出場できます。JAG夏合宿とは、そのアジア地区大会に向けた練習会みたいなものです。難易度はアジア地区大会同程度を想定しているため、かなり難しいです。僕はLgeuさん,dayamaさんと、チームPICOPICOPONで出ました。

3日間で5時間コンテストを2回、4時間コンテストを1回行い、それぞれ1時間前後の解説があります。ついでにAtCoderやCodeforcesのいつものコンテストも大体夜に開催されるので、文字通り競プロ漬けの3日になります。

この記事はその体験記です。僕の主観で、チーム全体の動きを書きます。主語が無い文章は大体僕のことを示しています。出題内容のネタバレが含まれているため、ネタバレNGな方はここでブラウザバックしてください。


day1

ICPC練習

前日何故か夜更かししました(は?)。4時間しか寝ずに会場に向かいました(え?)。5分遅刻しました(おい)。何だかんだありましたが、まずは成績は以下のようになりました。なお補足情報として、A,B,Cは一番簡単な3問で、D以降は難易度順はランダムです。

流れは次の通りです。なお最初の括弧は、コンテスト開始からの経過時間です。

  • ( -10分) 眠いと言いながらもとりあえず、dayamaさんがA問題、僕がB問題、LgeuさんがC問題を解いて、その後D以降を空いている人が読んでいく流れにしました(問題文が英語で、最悪でA4一枚分あったりするので、読むことは大事)
  • (11分--A) dayamaさんがいつの間にかA問題を通してました(AC)。その後D問題に取り組んだらしいです。
  • (17分--B) 僕がBで計算量が6000万の解法を思いつきました。C++の速度を信じて投げると通りました(AC)。その後E,F問題に取り組みました。
  • (60分--C) LgeuさんがC問題で少しバグったらしいものの通りました(AC)。多分G問題以降のどこかに取り組んでたはずです。
  • (81分--D) dayamaさんがD問題でバグります(WA)。
  • (108分--E) 僕がE問題分かんないと言っていた所、dayamaさんが「log付けたら行けない?」って話したので実装します。WrongAnswerが生えました(WA)。
  • (115分--D) dayamaさんが知らない間にD問題を通してました(AC)。
  • (130分--J) Lgeuさんとdayamaさんが考えているのを横目で見ていたら、いつの間にか通してました(AC)。
  • (157分--E) 僕が「E問題でlogをつける解法は詰み!」と言っていると、Lgeuさんが「素数MOD3つ組み合わせたHash化で十分では?」と話してくれます。僕が「それで上手く行くの?」と言いながら実装しました。WrongAnswerが生えました(WA)。Lgeuさんに泣きつきました。
  • (169分--E) dayamaさんに「実は非連結だったりしない?」と言われ確認してみるとマジでした。非連結用に書き換えると通りました(AC)。Lgeuさんに謝りましたorz。
  • (262分--K) dayamaさんがGを考えているのを遮って、僕が「K問題簡単では?二次元いもす法で一瞬っぽそうな香り(大嘘)」と言って邪魔をしました。どう考えてもO(250^4)で計算量削減出来ないと嘆きました(僕、邪魔しかしてないですね。反省します)。すると横でLgeuさんが「FFTじゃ?」という神のお告げを与え、dayamaさんが実装すると通りました(AC)。
  • (隙間時間--H) 僕はH問題を、Lgeuさんとペアプログラミングならぬペア考察を2時間ほどしてました。片方が考察を進めたら、もう片方がその先の考察をするというしりとりっぽい感じで解法が完成しました。実装が多分間に合いそうにないので、Kの応援をしていたら実装せずに終わりました。
  • (隙間時間--F) Lgeuさん「マラソンでは?」dayamaさん「三分探索」僕「F問題のAC少ないですね」K問題「実装に時間がかかります」H問題「何か解けそうです」F問題「ねぇ……僕を見て……」解説「三分探索です」チーム「あ……」

Codeforces

どうやらCodeforcesでコンテストがあったらしいです。5時間競プロをやった上に寝不足なので、ガン無視して寝ました。


day2

ICPC練習

Codeforcesを無視して寝たものの、いつもと違うベッドで寝ようとしたら夜中目が覚めてしまいました。結局寝不足です(2日連続)。そんなことはさておき、結果は以下のようになりました。めっちゃ順位が高いですが、実は1つだけアなことがありました(後述)。

流れは以下の通りです。なおday2は難易度が全問題ランダムなので、dayamaさんが先頭付近、Lgeuさんが中央付近、僕が後方付近の問題を読む戦略になりました。問題文は日本語になったので、非常に心が楽でした。

  • (12分--A) dayamaさんが、気が付いたらAを通してました(AC)。
  • (20分--E) Lgeuさんが「ギャグwww」と叫びながらEを通してました(AC)。
  • (53分--D) 知らない間にDが通ってました(AC)。多分dayamaさんだと思うけどよく分からないです。
  • (86分--I) 僕がIを場合分けを無限にして実装するとWrongAnswerが生えました(WA)。
  • (105分--I) 僕が誤読に気づいて修正すると通りました(AC)。その後黄金色の風船が配られて「FirstACは逃したけど2番目だーー!!」と喜びました。すると5分後に運営が「I問題はジャッジが壊れていることが判明しました」と話して風船を回収されました。実は僕の解法は嘘解法で、本来はWrongAnswerとなるコードでした(Game Over)。AOJの仕様上(?)、ACしたままコンテストが終わりました(不正過ぎる)。なおこの日に僕が通したのはこの問題だけです(か~な~し~みの~む~こ~う~へと~)。
  • (145分--C) dayamaさんがCの天才的閃きをしたらしく、勝利の雄たけびを上げながら実装すると通りました(AC)。
  • (273分--F) LgeuさんがF問題を解いていると「一般グラフの最大マッチング」に帰着できたものの、ライブラリを持ってないとチーム全員で嘆いてました。僕はIのリジャッジが終わらず嘘解法じゃないことを願いながらそわそわしてるついでに(願いは届かなかったけど)暇なので蟻本読んでると、tutte行列を見つけたので「こっちのほうは実装出来そうですか?」とdayamaさんに聞いてみました。実はそっちは出来そうだったらしく、しばらくして通りました(AC)。
  • (隙間時間--J) 僕は、I問題の様子が分からないのでひとまずJ問題を読みました。攻守のイメージを持ちながらLgeuさんに問題文を説明していると、貪欲法をしなさいと書いてあることが分かったのでその通りに考察しました。すると勝利条件が3つ生えて、dayamaさんが2つにまとめました。片方が余裕で片方が地獄だったものの、何やかんやして僕が地獄をファウルハーバーの公式に帰着しました(ファウルハーバーの形だとは知りませんでしたが……)。するとdayamaさんが「解きたくは無いけど出来るよ」と言ったので実装を投げました。しかし時間が足りなくてデバッグが終わりませんでした……。

AtCoder Beginners Contest 141

2日目夜の懇親会の終わりに「僕は眠いんだ!ABCには出ずに寝るぞ!!!」と叫びながら宿泊施設に戻りました。同室の人から「半分以上の人は出るっぽいよ」と言われたのでやっぱり出ることにしました(意思が弱すぎる)。

JAGとは無関係なので大きく割愛しますが、ABCDEの5完(306位)でした。E問題では10分くらいで「ローリングハッシュを張ってにぶたんじゃん~」という感じだったものの、「蟻本のローリングハッシュ、どこを写経すればいいんだろう?」って呟いていたら、38分かかりました。F問題は天才向けなので、非天才の僕は52分程度では分かりませんでした。レートがちょっと下がりました。

終了時刻は22:40でしたが、お風呂の入浴時刻が23:30までだったので、Twitterの感想戦を素早く切り上げてぷかぷか浮いてきました。


day3

ICPC練習

2日目夜にきっちり7時間くらい寝られたので、割と目が覚めて健康的な生活を送れました。それはさておき結果のほどは、day1,2に比べると下がりました。原因は明確なので後悔はしていませんが、C++が嫌いになりました(後述)。

流れは以下の通りです。難易度がday1と同じでA,B,Cが簡単、他がランダムなので、dayamaさんがA問題,僕がB問題,LgeuさんがC問題に取り組むことになりました。問題文が英語に戻ったので泣きながら読みました。

  • (7分--A) 相変わらず、知らない間にdayamaさんがAを通しました(AC)。
  • (29分--C) Lgeuさんが、簡単らしいとのことで実装してるとWrongAnswerを生やしました(WA)。 
  • (43分--B) 僕がB問題を見ると、セグ木を使うように見えたのでdayamaさんに押し付けようとしたところ、制約が特殊なおかげで愚直なにぶたんで通ることが判明しました。自分で実装してみたら通りました(AC)。
  • (59分--C) 誰かがC問題のバグの原因を見つけたらしく通りました(AC)。

ここから悪夢の始まり

  • (60分以降--色々) dayamaさんがD,E問題が解けそうで解けない顔をしてました。そこで僕がF,G問題の内容説明をすると、F問題が解ける気がしたので考察に入りました(え)。当然解けないのでdayamaさんがD,E問題に戻り、僕がH問題を読みます。LgeuさんがI,J問題を読んでると、I問題が解けそうな気がしたらしく、I問題を考え始めました。
  • (164分--H) 僕がH問題を読んでいると、オーダーがヤバそうなので、葉の方から順番にやらないと間に合わない気持ちになります。そこで「木DPか?」と嘘解法をつぶやくとdayamaさんが「いや、子のノードの答えは使いまわしは無理でしょ」と止めてくれました。すると何となく木上でノード毎のUnionFindが思い付いて、実際にサンプルで実験すると全部答えが正しかったのでdayamaさんに投げました。書いてもらってる間にマージテクじゃね?って横やりを入れながら実装してもらっていると、WrongAnswerが生えました(WA)。
  • (167分--H) バグを直します。WA。
  • (171分--H) 更に直します。WA。
  • (183分--H) 直す。WA。
  • (184分--H) 直す。Runtime Error。地獄の始まり。配列外参照やMLE、無限ループや再帰によるスタックオーバーフローなどを予想する。
  • (195~226分--H) Runtime Errorが消えない……(×9回)。assertをくっ付けて原因究明してみたが、全然分からない。
  • (236分--H) 僕が、終了5分前でキレ気味になりながら「せめて原因分かりたいから……ね?」とassert"だけ"を13個埋め込む。なんかジャッジ時間が長くなる。dayamaさんが「assert重いんじゃない?」と呟いているとACする(は?)(AC)。
  • (after contest) 原因は分からずじまいでしたが、多分「C++の未定義動作を踏んでAOJ側で強制終了」したという意見になりました。assert"だけ"埋め込むと動いたということはそういうことだという意見が多かったです。なお 始祖のRuntimeError にassertを11個埋め込んでみるとACしました。謎の1時間でした。

あとがき

色々ありましたが楽しかったです。ただ1つ反省点があるとすれば、「ちゃんと寝よう」です。アジア本番では前日にちゃんと寝た上で参加出来たら良いなという知見が得られたので、良かったです。