足跡-sokuseki-

りかの日進月歩の記録

JAG夏合宿2018 / 会津合宿2018 参加記

参加記 競技プログラミング

9/15から1週間の競プロ旅行をして、JAG夏合宿2018（2018/Practice/夏合宿/案内 - ACM-ICPC Japanese Alumni Group）と会津合宿2018（会津大学競技プログラミング合宿2018 : ATND）に参加してきました。コンテストの時系列はだいぶあやしいので間違っていてもゆるしてください。

9/15 (JAG day1)

参宮橋でびーとくんと松屋に行き、うしをたべる。

集合場所に行ったらそこそこ人がいた。
とりあえずみくにゃんのとなりにすわる。まえにfour-tがいた。
コンテストは去年の台湾セット。priMe.caTで出る。

コンテストが始まる。みくにゃんがテンプレ、ぼくとtm先輩が手分けして問題を読む。
AとBを先輩、Cをぼくが読む。Aがやるだけなのでみくにゃんが書いてAC。
Cはいもすをすればできそうなのでみくにゃんに伝える、a_iが大きいから配列には持つことができないし、mapを使えば良さそうということでAC。
Bもやるだけなのでみくにゃんが書いた。ここで30分経過。
Dを先輩、Eをぼくがよむ。Dは愚直にやるだけなのでみくにゃんが書く。Eは幾何。Dを提出するとTLE。うーんってなりながらEの問題をみくにゃんに説明すると、多角形の頂点がのる円の半径を二分探索すればうまくいきそうなことがわかり、Eを書いてもらう。tm先輩はFを読んで実験していた。Eのサンプルがあったところで提出するとWA。tm先輩がFの実装を生やしてくれたのでみくにゃんが書く。WA。Eは多角形が円の中心を含まない場合がまずいのではないかと気づく。提出するとWA。おかしい。Fはmodをとる値を間違えていたことがわかったので直してAC。Eわからないなーとなって、Dを考え直す。mapを使ってシミュレーションをしていたけど、stackとqueueを使ってもできるのでそれに書き換えて提出するとAC。残り40分ほど。GのAC数がそこそこあったので、ぼくとみくにゃんがEを考えている間にtm先輩にGを読んでもらう。なんだかんだでそのままタイムアップ。
ABCDFの5完でした。
そのあと解説が始まる。解説者を公募するのおもしろかった。Dはarcsinがまずかったのかなあ。

そのあと宿舎に移動。これは迷子になりますねという感じ。
おへやでまったりしてからみくにゃんとよるごはんを食べにいった。サラダ食べ放題だった。サラダ食べ放題。やさい。

帰りにコンビニに寄ったらおみやげがいっぱいあった。アイスの種類が豊富ですごいなーってなった。
おふろに行ったら広くてびっくりした。
おへやにかえってAGC。爆死。レートくんいままでありがとう。（レートとビートって似てない？）

9/16 (JAG day2)

夏合宿の朝は早い*1。7時におきた。8時前くらいにみくにゃんとせいかちゃんのへやのひとと食堂にいく。やさいをたべる。

部屋があいてなかったのでみくにゃんとコンビニにいく。ひとがおおい。
センター棟に戻ると部屋の前で開くのを待ってる人がいたのでAGCの感想戦をしたりする。

オタクTシャツを着ている人が複数いてウケるなどする。
チームメンバーがきまっていないので運営の手を借りチームを決める。apollopiaのmtsdさんとatsさんになる。メンバーが東大生2人（橙と黄色）でこわいなあ。でもチームに貢献したいという気持ちになる。

コンテストが始まる。Aを読む。いろいろ考えるとz全探索すればいいんじゃね？となる。ただ数学力のNASAのせいでどのくらい探索すれば答えがでるのかわからない。つらいなあという気持ちになっているとBが通る。手があいたmtsdさんに尋ねると17*107程度だからすぐ終わると言われてはいとなる。数学ができませんでした…みたいな気持ちになりながら実装してAC。その後すぐatsさんがCを通す。
その後、軽く全体に目を通すと、Dはリアクティブで入出力がうくそうで、Iがデータ構造ゲーな感じがするのでやめる。それ以外を分担して読むことにする。
ぼくはHの考察を担当して、禁止文字列を数え上げして全体から引くほうが簡単な気がしてくる。禁止文字列はSuffixArrayの気持ちになると数え上げができるので、mtsdさんに方針を伝えるとライブラリ写経を含めすべて実装してもらえた。AC!!!その間にatsさんがEの考察を詰めていてくれていたみたいで、すぐにEの実装がはじまる。
えーなんかここらへんの記憶が定かじゃないんですが。
Kはできそうな雰囲気なんですが考察を詰めると意味がわからなくなります。
Gは重心のあたりをいい感じに探索すると見つかるのでは？という嘘解法が生えます。（それと同時にダメなケースも生えます）
Fは2直線の交点を求めていくんですが、サンプル2で誤差死します。
Jはよく考えるとマンハッタン距離みたいな感じになって解けるということをatsさんから聞きます。実装してもらいます。ACします。すごすぎる……。
その後進捗が特にないままコンテストが終了します。
解説のKやばくないか？

夕食まで時間があったので談話室で杏ちゃんを降臨させたりします。夕食にいきます。



ごちうさの3期が決定したりします。
お風呂に入ったあと、談話室で精進(?)をしながらボドゲ勢を眺めていた。12時くらいに解散になる。SuffixArrayをちょっと勉強して寝る。

9/17 (JAG day3)

朝起きるのがつらい。7時におきたんですが、おきてすぐ朝食にいくのつらくないですか？
キャベツを無限にたべた。シーツ回収にも無事まにあったのでよかったね。


時間があったのでらいぶぱーちーをする。

コンテストはpriMe.caTで出ることになったんですが、コンテスト開始10分前にpcが更新して再起動をはじめやばい雰囲気になる。

コンテストがはじまったので、3人でABCをよむ。pcの再起動がおわって、問題を把握した順にB,C,Aをみくにゃんに実装してもらう。3ACした段階で30分くらい経過していた。
そのあと、順位表からIが解けそうだということがわかって、みくにゃんとtm先輩がIの考察、ぼくがその他の問題の問題概要を把握する係をする。Iの解法がはやめに生えたので、みくにゃんがIの実装をはじめる。IがACしたタイミングでJが解けそうな感じがしたので3人で考察する。偶奇で場合分けすればできそうとわかる。みくにゃんに実装をまかせる。AC。みくにゃんとtm先輩がFの考察をする。解法が生えたのでみくにゃんが実装する。AC。ぼくはずっとDを考えていたんですが、順位表をみてUKUNICHIAがFAしているのがわかり、これは文字列ではなくセグ木とかのデータ構造を使うのでは？という気持ちになる。w_iをそのままソートしたもののインデックスの配列と、w_iをreverseしてからソートしたもののインデックスの配列を作って、クエリごとに「[l1,r1]と[l2,r2]に共通するインデックスの個数は？」に答えるという言い換えができることに気づく。みくにゃんにそれを伝えるとBITでできるという話になる。みくにゃんにがんばって実装してもらう。AC。tm先輩はその間Gを考察していて、実装がおわったみくにゃんも加わって考察して、DPをすればできそうという気持ちになる。ぼくは順位表をみて敬遠していたEHKの読解をする。幾何幾何数列で解くなら数列かなーという印象をうける。みくにゃんがGの実装をはじめて、Kをtm先輩と考察する。Gがサンプル合わなくてつらい感じになる。そんな感じでコンテスト終了。
ABCDFIJの7完。

解説の後、部屋で駄弁るをしていた。部屋から追い出された後もロビー(?)でずっと喋っていた。
オリセンから出た後、JOIer御用達と教えてもらったラーメン屋を見つける。お腹が空いていないため立ち寄るのはやめた。

JAG合宿は終了です。「ACPCでまた会おうな！（なお2日後）」というのをした。

9/18 (JAGとACPCのあいだ)

はむこさんと巣鴨のラーメンを食べに行って*2芥川龍之介のお墓を観光する。

会津に向かって出発する。電車の乗車時間が長すぎる。




9/19 (ACPC day1)

13時に集合ですが学食を食べたい気持ちになったのと運営なので早めに行く。9/19であることに気づき、食堂でチーズカツカレー*3を食べたい気持ちになる。が、チーズがないのでカツカレーを食べます。うしくんと宝くじをいっしょにひくをします。6等なんですが…。
会津合宿がはじまります。自己紹介フェーズでは本名を言うだけで周囲の笑いを生やす人がいてすごいなあとなる。運営なのでチーム決めを見守りますがチームを事前に決めている人がいないことに驚く（内心、これはオンサイト全完は出ないな…という気持ちになる）。
会場が2つの部屋に分かれているらしいことを聞く。風船を運んだりするの面倒だなあという気持ちになる。
コンテストが始まる。30分くらいは風船運びがめちゃくちゃ忙しかった。
最後のFGHが全然解かれなくてやばいなあという気持ちになる。GはオンラインでACが出たけどFHは解かれないままコンテストが終わる。
解説も終わって、うしうくびーとと一緒にラーメンを食べに行く。解散してホテルに戻ってぼーっとする。風呂に入って寝る。

9/20 (ACPC day2)

8時におきる。うくにきあ。朝キャベツをたべる。おいしい。
大学につくとうしくんがいたのでらいぶぱーちーをする。たのしい。こたつがめと同僚になった。同僚に対して同僚申請お願いしますを連打しがち。
チーム決めは運に任せることにする。ツカサさんとやまさんとチームを組む。
レート順にやまさんがA、ぼくがB、ツカサさんがCをやることにする。

コンテストが始まる。Bを読んでいるとAがACされる。1分半。早解きが得意すぎないか。（あとで順位表をみたらみんなはやかった、世界がこわれてる。）Bわからない、Cもわからないらしい。3人で少し考えたあと、ぼくとやまさんでAとBを一緒に考えて、ツカサさんにDを考えてもらうことにする。DはBFSをやるだけらしい、実装をたのむ。AC。BとCがわからないなあとなる。Eをツカサさんに読んでもらうと2つの長方形の中心を通る線の傾きを求める簡単な問題であることがわかるので、実装してもらうことにする。AC。Cはスワップクエリのたびに区間の数が増えていくと思っていたら、実は各クエリ後は区間の数を2にすることが可能であることがわかるので、数列の一番最初の数だけ持っておくことで解ける。実装をやまさんに任せたらACした。Bは人数が多いチームが相手のライフを2ずつ削っていき少ないチームが相手のライフを1ずつ削っていく戦略が最適であることがわかる。サンプルを見るとターン数はそこまで大きくならないでしょという気持ちになるので、シミュレーションぽいことをしたくなる。実装をやまさんに任せるとACしていた。Fをツカサさんに読んでもらっていたら、基本はダイクストラで、辺のコストは三分探索で求めるという方針が生えたらしい。それでいけそうな気持ちになったので実装を任せる。その間にぼくとやまさんでGとHを読む。サンプルをかきかきする。わからないなあという気持ちになり険しい。Xijの制約が怪しいのはそうなんだけどなあ。Fの実装が終わったところで提出するとTLE、三分探索のループ回しすぎじゃーんとなる。WAになる。WAの原因がわからないとなる。ツカサさんにもGとHを考えてもらうことにする。G計算量をO(NM)から落とす方法が思いつかなくてHを考える。グラフにして閉路をなくすために消す頂点の最小個数を求めたくなる。閉路が重なっている場合、いい感じの頂点を消したいなあとなると、閉路のインデックスの区間の重なりが多いところを消したくなる。区間スケジューリングでは？となる。ツカサさんが実装してくれるらしいので任せる。
ツカサさんがHを実装している間、ぼくとやまさんはIを読むことにする。文字列の問題だけどアルファベットを頂点とするグラフに置き換えられるよねとなる。入次数＞出次数となる頂点は必ず答えになることがわかる。入次数＜出次数となる頂点は必ず答えにならないことがわかる。入次数＝出次数のときどうするねんとなる。そうこうしているうちにHが通る。Fを考える。ソースコードを読んでも間違っているところがわからないがもしかして三分探索が原因か？となる。doubleじゃなくてlong long を使うことにする。テストケースが60まで進んだが？？？？しかしその先がわからない。あきらめてIを3人で考える。いろいろ考えてもわからねえとなる。ラスト20分くらいになって時間ないしやっぱりFを通したいなあとなる。三分探索の結果プラマイ10くらいの最小値をとるとACした。つらいね。ABCDEFHの7完でコンテスト終了です。
解説後のスポンサーセッションで寝ている人を観測するのが楽しかった。
懇親会会場まで歩く。雨がきつくなくてよかった。懇親会ではテーブルが知っている人だらけになる。ウケるなあ。
いろいろなおはなしをした。ハイテンションになってやばかった。うくにきあおもしろすぎないか？酔いつぶれている人を複数観測してやばそう(他人事)となる。22時くらいまで謎テンションを繰り返す。その後ホテルに帰った。風呂に入って寝る。

9/21 (ACPC day3)

6時半におきる。朝キャベツをたべる。ホテルとも今日でお別れ。ちょっとさびしい。
軽く雨がふってたけど大学まで歩く。


チームメンバーはすでに決めていたのでチーム決めフェーズは外に追い出される。
うくさんとうしくんと組む。うしくんにたくさんFAをとってもらいたいという作戦。コンテストが始まる直前までうくさんがアズリムの動画を見ていた。アズリムかわいいなあとなる。

コンテストが始まってうしくんにAを任せる。ぼくがB、うくさんがCをよむ。Bは昨日のCに似てるなあとなるがわからないね。うしくんがAに手こずっている。うくさんからCの概要をきく。abどちらかが閉路に含まれていない場合は1、両方含まれている場合は2とわかるね。うしくんがAを通してすぐCの実装をしてもらう。うくさんがD、ぼくがEを読む。Eは解法がわからないけどグラフの問題だからうくさんが得意そうと思う。うくさんにDをきくと区間スケジューリングか？となる。うしくんがCを通す。実装はやい。Dをうしくんと相談するとDPでいけるねとなる。うしくんに実装を任せる。Eをつめると強連結成分分解をすると木を2つに分ける問題になってDPぽくできるねとなる。うしくんがDをACしたのでEを実装してもらう。FとGをよむ。Fはむずかしそうとなる。EがWAったので印刷をしてうくさんがデバッグをする。うしくんにFとGを伝えるとFはわからないけどGはいけそうなかんじ。Eが実装の順が逆(?)だったみたいでなんでサンプル合うねんとなる。EがACする。うしくんがGをかきはじめる。ぼくはFのサンプルを書いて実験してみる。うくさんがBを考える。Gが通る。うしくんすげえ。なんかDPをやったらしい。順位表からBはだいぶ通されていたのでなんとかしてBを通したい気持ちになり、うしくんとうくさんがBを考える。クエリ平方分割とかいうのでできそうとなったらしい。Bとは…となりながらうしくんが実装。大変そう。Bが通る。ACしてよかったけどこれ本当にBか？となる。残り1時間でみんなでFを考える。とりあえず一番左から確定していくので、O(Q|S|)でできないか？となる。シミュレーションしたいなあとなるがむずかしいね。順位表をみるとオンサイトで全完がでる。ペナルティを計算すると、時間内にACすればオンサイト1位になることがわかる。うしくんとうくさんがペアプロぽいことをする。ぼくはがんばれーと念を送って応援する係をする。WA。残り10分ちょっと。場合分けをする。WA。場合分けをがんばる。ラスト1分を切り焦りながら提出するとAC！全完です！！！！！
コンテストが終了し、全体2位、オンサイト優勝がわかる。いえーーい！！
うれしさにつつまれながら解説をきく。Bはリストをもつらしい。なるほどなあ。Fは木になるのでLCAをするらしい。天才か？
ACPC2018はこれにて終了ですというアナウンス。廊下にでてお菓子を食べながらこたつがめさんとかに雑な絡みをする。うしくんといっしょに駅までかえる。駅でデレステをする。電車がきたのでのる。ねむいね。JAGとACPCの参加記を書きながら、2つの合宿で1問しか実装しなかったことがわかる。明日コドフェス予選ですが大丈夫ですか？という気持ちになる。
郡山で松屋に入り、うしくんの活躍を讃え牛めしをたべます。おいちい。食べ終わって、うしくんとおわかれをして、新幹線にのります。旅は終了です。

感想
とても濃くて楽しい1週間でした。みなさんありがとうございました！
あと途中でtwitterのリンク貼るの面倒になりました。まあごはん情報は誰も欲していないはずなので。

*1:夏合宿の朝は早い | Aizu Online Judge。特にこの問題を貼った意味はないです。

*2:ラーメンの写真をツイートするのを忘れていたみたいで悲しい

*3:2014/9/19にモバマスに桐生つかさが登場し、桐生つかさがよくチーズカツカレーを食べていることから、9/19にチーズカツカレーを食べる風習がある。なお桐生つかさはチーズカツカレーについて「最強だな」「チーズカツカレーを考えたやつは天才、なにより美味いしな」と語っている。