JAG夏合宿2019参加記 - kort0nの日記

JAG夏合宿2019に参加しました

行きの電車内で宿泊所が咲の聖地だということを知り、少しテンションが上がる特に何もしなかったんですが

https://twitter.com/ILoveTw1tter/status/1172700481526779904?s=20https://twitter.com/ILoveTw1tter/status/1172700481526779904?s=20https://twitter.com/ILoveTw1tter/status/1172700481526779904?s=20

清澄高校 pic.twitter.com/4xMWCT9yC9
— こるとん (@ILoveTw1tter) 2019年9月14日

https://twitter.com/ILoveTw1tter/status/1172700481526779904?s=20https://twitter.com/ILoveTw1tter/status/1172700481526779904?s=20https://twitter.com/ILoveTw1tter/status/1172700481526779904?s=20https://twitter.com/ILoveTw1tter/status/1172700481526779904?s=20

最初の参加者自己紹介のときに「risujirohはまだ来てません」と言う羽目になったこういうの言うの恥ずかしくないですか？遅刻しないで

Day.1 okimochi(kort0n, risujiroh, idsigma)

PCとキーボードを並べると思ったよりスペースが狭いので、運営の方に許可を取った上で机を繋げる社会性の欠片も無い感じになる

とりあえず

A:idsigma

B:kort0n

C:risujiroh

で読んで、分かった人から実装しようとなる

読むと分かったので実装して通すそこそこ速かったのでFAかな？とわくわくしていたが、four-tに1分差で負けていたゆるせねえ...

A,Cは暫く掛かりそうだったので、後ろの問題を一通り読むことにする

後ろを読むとH,J,Kの解法が生える今日冴えてるな〜天才だな〜

risujirohにCの相談をされる話を聞いていると自己解決していた良かった(?)

その後idsigmaさんがAを通す Kの実装を投げると、問題文の誤読を指摘されて解法が爆発したは？

JはUnionFindとフローの写経が必要なので後回しにしたかったが、流石にHより楽なのは明らかなのでこれをやることにする伝達も面倒なので自分でやることにする

risujiroh「写経しようか」

kort0n「いや、自分で写経するわ」

と言ってドヤ顔でコーディング席に座ったところで、(普段使い慣れていない)US配列キーボードであることを思い出す

kort0n「ごめん、写経頼むわ...」

写経パート以外は軽いので、写経してもらうと流石に通る

Dをrisujirohと詰めていると、連立合同方程式を解けば良いということが分かる書けますと言われたので任せると通る

満を持してHの実装に入る大まかな解法は以下の通り

列は、B列ずつM/Bブロックに分ける
各ブロックについて、対応するbの値をvectorに突っ込んで、ソートしておく
N*(M/B)個のブロックについて、書かれる数字の数を計算するこれは、さっき作ったvectorを使って二分探索すると、1ブロックあたりO(Blog(max a_i) * logB)で出来る
クエリをdの値昇順で処理するブロックは適当に飛ばして、各ブロック内では真面目にやる

(これ改めて見ると計算量ダメですね...これでやってはいけない...)

H実装中に他の2人がEを詰めたらしく、解法を共有されたので、「ただしそう」と言う「log取るか素数mod取るか」とかでちょっと相談したら、誤差ヤバいしlogはダメだねとなる実際logでやろうとしてハマったチームもいたらしい logで解決したくなる気持ちはかなり分かる...

Hは実装終わるまでどうせ暫く掛かるし、一旦PCを譲る最初modを1つのみでやってWAを吐くも、modを2つにしてrisujirohが通すなんか有名素数は対策されていたらしく、有名じゃない素数mod1つで通したチームもいたらしい？

再びHに戻る実装をして投げるとTLE 桁数を求める関数を極僅かに高速化したり、バケットサイズを適当に調整したりして何度か投げるもTLE

risujirohがKは二次元畳み込みで解けますと言う Hは泥沼感が出てきたので代わるとKが通る

再びHに戻るバケットサイズの調整の為に、前半パートに掛かる時間等が知りたくなるこういうときはsubmitデバッグが便利なんですね

submitデバッグをすると、なんかバケットサイズとかの問題じゃなくて計算量落とさなきゃ無理なのでは？という気がしてくるここでHを諦める何とTLEとsubmitデバッグを含めて14submit... PC長時間占拠したしこれは完全に戦犯ムーブでしたね...

順位表を眺めると、Gを通すべきだという話になる考えても何も分からない

risujirohがdpテーブルは想定解通りにちゃんと定義出来たようだが、実装ミスか遷移式ミスか何かで一生サンプルが合わず、コンテストが終了する

結果は7完最速の8位(オンサイト4位)で冷えっ冷えだった誤読嘘解法人に投げるし写経要求で人の時間奪うしHで一生PC占拠するし、完全に戦犯をした...

コンテスト後てんぷらさんに「おきもち冷えすぎだろ」と煽られるキレそう

解説を聞く Hで浮動小数点数的な考え方をすると計算量がlog(max a_i)落ちるのか〜天才だな〜

感動しながら再実装して投げる

f:id:kort0n:20190916225514p:plain — やーめた

コドフォに出たかったが、回線難民で出られなかったので、談話室のボドゲ会に参加する楽しかった

最the高 pic.twitter.com/DDEOU1HYfD
— こるとん (@kyort0n) 2019年9月14日

海底探検の最終ラウンドで欲張って無事帰らぬ人となりました

Day.2 Seica_no_okimochi(kort0n, risujiroh, seica)

「後ろどんどん人増えますね〜」とか談笑してたら突然前に人が増えて非常に厳しい気持ちになった
— こるとん (@kyort0n) 2019年9月14日

idsigmaさんは私用で不在につき、seicaちゃんをチームに招き入れる

問題が難易度に依らず全問シャッフルらしいので、とりあえず各人がmod 3で問題に目を通すことにする

自分はA, D, G, Jを読むことになる Aが簡単なので取り組むことにする

連結成分を調べたいのでUnionFindを写経する見事5箇所ほど写経ミスする US配列を許すな

写経が終わると流石に通る seicaちゃんが「Eがギャグ」と良い、サッと通す

Dが解けたので実装する肺が0個と判定されたときの出力を誤って1WAするが通る

Fを考察していたseicaちゃんが、「†一般マッチング†に帰着された」と言い始める嘘だろ？と思いつつ話を聞くと、†一般マッチング†に帰着されたことが分かるまあこの問題固有の上手いやり方があるかもしれないし、手を付けるかはオンサイトAC状況を見つつ決めようという話になる(オンラインACはライブラリコピペで終わるので参考にならない)

CGHJあたりを適当に読んで考察する Cは何となく最小費用流っぽい話になりそうだなーと感じる GHJは何も分からない...(Jの勝利条件が分からないのは流石に酷すぎる)

risujirohがIを解いて実装する WAを連続で出していて辛そう暫くすると解法を共有される

聞いた感じ合ってそうだけどなー「あまり通ってないし、とりあえず後回しにしよう」と言ってトイレに行く戻ってくるとジャッジミスがあったらしいと言われるかなしいね

暫くすると、seicaちゃんがjの最適戦略を導き出すこれを使って勝利条件をまとめる最初自分のミスで20分くらい無駄にしたは？

勝利条件を元にして、seicaちゃんが答えを表す式を立てる変形するとN-1乗和の公式に定数倍掛けたものを足したり引いたりした形に変形出来ることが分かるので、多項式補間で出来ると分かるこれをrisujirohが実装する

暫くサンプルが合わなかったが、標本点を選ぶ際に偶奇性に注意しないといけないことに気付いてサンプルが合う AC これは熱かった

Bについて話し合うが、全員口を揃えて「これ最大流問題を部分問題として含むし、フローは明らかに無理だし、何かおかしくないか？」と言うということでclarを投げる

f:id:kort0n:20190916235350p:plain — 仰る通りでございます。

「全てのedgeのcapが等しいならdinicは速い」ということを知らなかったせいで、このようなクソclarを投げてしまいました。clar対応の皆様、本当に申し訳ございませんでした...

Cを改めてちゃんと詰める最小費用循環流っぽいことをやればokだということが分かる Primal-Dualの写経をrisujirohに頼んで、Cを実装する添字ミスで1WA吐くも無事AC この時点でオンサイト1位になって思わず叫ぶ

Gを詰めていたseicaちゃんが実装に入る risujirohにO(N^2)でいいからHのdp解を書いてみてくれと言われるちなみに一旦計算量の悪い解を僕が書いて、その数式をrisujirohが変形して高速化するというのは弊チームの常套手段で、RUPC2019 day3の赤黒そーるじぇむでもこういうことをしていました

O(N^2)解のdp遷移式を立ててrisujirohに渡すこの時点で残り時間は30分ほど計算量が落ちたときにすぐに実装出来るように階乗逆元等の準備も兼ねて、埋め込みも視野に入れつつ、Gで辛そうだったseicaちゃんにPCを譲ってもらって、HのO(N^2)解を書き始める

この辺りで(これまで完答数が並んでいた)右前のHeno_Worldに風船が届けられる様子が視界の端に映って絶望する

O(N^2)解を書いている途中で、risujirohが期待値の式をO(N)で求められる形への変形に成功するしかし二乗和の期待値は間に合わず、6完で終了となった

f:id:kort0n:20190916233007p:plain — 6完最速全体4位オンサイト2位

7完のHeno_Worldとの差はFだったどうやらFが一般マッチングになるという考察は間違っていなかったようなのだが、Heno_Worldは一般マッチングライブラリが無いにも関わらず、その場でフルスクラッチで書いたらしい heno_codeとかいう男気持ち悪すぎる本当に無理だ

僕がどう見ても一般マッチングだからやめろって言ってる横でやむなくくんが提案したアルゴリズムをへのくんが実装して通していたので本当に意味がわからない
— てんぷら (@tempura_cpp) 2019年9月15日

コンテスト後は懇親会があったやはり(日経コンやDDCC等の規模のものと比べて)参加者が少ない懇親会は、色々な人と話そうという気分になれて良いですね

choKOdaiの方々とお話し、「高速ゼータ変換は名前が格好良い」という話で盛り上がる高速ゼータ変換って格好良くないですか？

突然じゅっぴーにじゃんけんを挑まれたので戦って勝つと、大量の名札を押し付けられた上に、カツアゲ呼ばわりされるなんで？

JAG懇親会、友達みんなこるとん(@kyort0n )さんにカツアゲされた(இдஇ; ) pic.twitter.com/ktTFB1ofp2
— じゅっぴー (@juppyjappy) 2019年9月15日

懇親会後はwriterを務めたABCがあった談話室で大勢の人が参加していたので、同じくwriterだったbeetさんと眺めていた

????_code「良い問題でしたね E問題だけに」

らてさんと初めてお会いするらてさんは完全に酔っ払っており、名乗ると突然

「うんこるとんじゃん！！！！！！！！」

と言われた(参考:TTPC2019参加記 - kort0nの日記)

その後5回くらい「やむなくさんですか？」と聞かれた「えーだって黒髪で眼鏡掛けてるし」と言われたやむなくは眼鏡を掛けていなくないか？

potetiさん曰く、らてさんはやむなくに会ったことが無いらしい何から何まで意味が分からない

Day.3 kaisan(kort0n, risujiroh, heno_code)

idsigmaさんとてんぷらさんが同時に作問チームに入っている日があることは分かっており、okimochiとHeno_WorldのContestantがちょうど3人であった為、組むことにした

こるとんさんにどんな問題投げればいいか分からねえ
— heno (@heno_code) 2019年9月15日

わかるなあ(得意ジャンルという得意ジャンルが無い人なので)

当日コンテスト会場に集まると、henoがビズリーチTシャツを着ているこれは...?

f:id:kort0n:20190917000828p:plain

f:id:kort0n:20190917000842p:plain

そう、これはHeno_WorldがICPC2019国内予選ラスト40秒でEを通し、我々から奪い取った(?)企業賞のTシャツであるゆるせねぇ...

「ふざけやがってチーム解散だ」と言うと、「じゃあチーム名解散にしましょう」と言われるこうして謎チーム名"kaisan"が誕生する何？

とりあえず

A:heno

B:kort0n

C:risujiroh

で読むということになるまた、D以降はhenoがメインのコーダーを務めるということになる弊チームは基本的にコーダー担当のような人はいない為、少し新鮮で楽しみ

henoはAがすぐに分かったようで、書き始める

自分も数分掛かったがBが分かる

risujirohにCの相談をされる無証明だが流石に正しそうな貪欲解法...

「実装量は多分同じくらいで、Cは解法が少し怪しいけどBは流石に合ってるからBからやろう」と言う

Aが通った後Bを実装するドヤ顔でsubmitする

f:id:kort0n:20190917001624p:plain — Cは解法が少し怪しいけどBは流石に合ってるからBからやろう

本当に死にたくなった

更に悪いことに、自分のコードのバグが見つからない最悪だが後ろを読んでいるhenoに相談して、デバッグをしてもらう

無事バグを発見してもらう Cをrisujirohが通した後、Bを通す 3完は2位以下に結構な差を付けたハイスピードで1位だったらしい

しかし、自分がhenoに相談して止めてしまったこともあり、ここで実装キューが空になるつらい

F(risujirohが得意そうなタイプの数え上げ)、G(期待値ゲー)、I(数学ゲー)は自分よりrisujirohに任せるべきなので放置自分はDEあたりを読むことにする「Dが燃やす埋めるで解けました」と言うと、henoに「この形は二部グラフじゃないと無理」と言われ、risujirohに「制約的に間に合わない」と言われるごめん...

risujirohがJのN=2べきでの構築に成功する 2べき以外で失敗することは証明出来てはいないが、まあそれっぽい結果だしとりあえず投げてみるしかしWA

相談も挟みつつ色々考えていると、自分とrisujirohでHの解法が生えるしかし実装が重そうだなぁ...

henoに解法を伝える

kort0n「でもこれどうやればいいんだろうね UnionFindでマージテクするけど、そのときそれぞれのUFに辺の情報を持たせて...」

heno「あ、実装方針は任せてください」

た、頼もしい...

そうは言いつつ結構時間が掛かるだろうし、とりあえず他の問題を読もう Dはよく考えると2-SATの形になるねでも辺がかなり多くなりそうで...

heno「サンプル合いました」

...は？

heno「通りました」

この男本当に無理だ気持ち悪すぎる

Jを考えると、それっぽい解法が生える N=4, 6, 8で手元で試すと正しく構築出来る

これをhenoに頼んで実装してもらうすると、N=10で破滅することが分かる死んでくれ

その後risujirohがGを解く henoが実装すると見事AC

再び実装キューが空になる henoも考察を始めると、henoがEを解き、実装を始める

自分は再びDに戻ると、辺を貼るパートが3^N全列挙で出来て、実は辺がそんなに多くならないことが分かる

risujirohがIを考察すると、綺麗な畳み込みの式になって解決する(僕としてはこれが解けるのもかなり気持ち悪いんですが...)

何とここに来て3問ほぼ同時に実装キューに突っ込まれるこれは興奮した

henoがEをバグらせた為、印刷して一緒にデバッグをするその間にrisujirohがIの実装を始める

一緒にデバッグをすると(結局はhenoがほぼ自己解決したのだが)バグが見つかり、Eを通すその直後にrisujirohがIを通すこれで単独7完で1位に

その後はhenoがDの実装を始める残り時間的にあとは実装が重い問題を解いても意味が無い為、解ければ実装が軽そうなJをrisujirohと考えるしかし解けない Dの実装も間に合わず、時間切れになる

f:id:kort0n:20190917005225p:plain — 7完で優勝！

AC数はeiyatonariと同じでしたが、ペナ差が効いて優勝しましたやったー

その後はJAGの方+potetiさん+risujirohと万豚記に行きました「茄子豚ピリ辛炒め」を注文したら、連続部分文字列であるところの「酢豚」が出てきました

#JAGSummerCamp2019 pic.twitter.com/SgXgbXzKV0
— こるとん (@kyort0n) 2019年9月16日

楽しい3日間でした JAGの方々、作問チームの方々、本当に有難うございました。