JAG夏合宿2019 参加記

いつもの

Day1

JAGセット

小遅刻。ごめんなさい。コンテストは僕、への、せいかちゃんで出ました。

・Bはてきとうに書くと通る。

・Cをへの、Aをかちゃんが通す。

・Eはdfsしてmod見たらいいねってことでへのくんに書いてもらう。modとり忘れたり全然違うmodをとったりして冷えてた。まぁ無事通ったのでよし(よくはない)

・Dは中国剰余定理だけどどんなにサボっても間に合う計算量っぽいのでひたすらサボる。コピペ禁止だとサボり力は大事なのでね。AC。

・Jもやるだけらしくてへのくんが書いてAC。

・Gの実装を始めるもちゃんと詰めずにPCが空いてるという理由だけで書き始めたせいで色々間違っててひどい目にあう。書く前にちゃんと詰めような...

・Hはとりあえず平方分割でできることはわかったのでGのデバッグと並列してへのくんに書いてもらう。

・Gのデバッグが先に終わってAC。Hは計算量怪しすぎるしブロックサイズガチャかなぁと思ったのになぜか一発で通る。へのくん気持ち悪い。

・IはCHTでできるので書き始める。途中でKの畳み込みという声が聞こえてきて冷静になると簡単だったので途中で実装を変わってKが通る。

・Iが誤差で死ぬ。デバッグが世界一下手。手元でテストすれば気づけそうなことに気づけないまま10ペナと1時間を費やしたのであった。完。

・Fはこんなの凸としか思えない、三分探索でできるに決まってると主張し続けていたのですがなぜかなかなか聞き入れてもらえませんでした(証明できなかったのが悪い)。完。

ペナ差でうくにきあに負けた。ありえねぇ。あとチームのために買ってきたお菓子の9割がへのに消費されていた。許せねぇ。

こどふぉ

前回のcombinedで相当冷えたから避けるか迷ったけど「こどふぉに出なさい💢」WiFiが飛んでたから出る。

 つまらん。

 

Day2

つくばセット

教習所から参加のやむなくも含めてHeno World で出た。

・Eてんぷら、Aへの、Dやむなく

・Fの嘘を書いて落ちる。Fが一般マッチングに帰着される。完。

・やむなくから「ぼくのかんがえたさいきょうのいっぱんまっちんぐ」が送られてきてへのくんが実装する。僕は無理だろっつって止めてた(この辺わりと空気が悪かった)。

・けっこうバグるのでJを割り込んで書いたりする。添字でバグらせたりmodでバグらせたりして最悪な気持ちになるけど一応通る。

・Fが通る。は？？？？？俺が悪かった。

・Iのジャッジが治ったので考えるとへのくんが解いてくれた。てんぷらこれジャッジが壊れる前にそこそこ考えて解けなかったのだめでは？

・途中教習で抜けてたやむなくにCを投げたらほどなくして答えが返ってきた。こわい。AC。

・Gのそれっぽいのをへのくんが書いたけど通らない。解説を聞いた感じわりと惜しい嘘だったっぽい。

 

7完でオンサイトでは1位、やったね。

 

解説を聞くとHが当然やんけという気持ちになる。ダメだなぁ。

 

ABC

完。

 

Day3

有志セット

writerの1人でした。

A　ほむほむ。開始後に投げられた最初の4提出がすべて落ちて笑った

B　原案ほむ。てんぷらは演算をちょっとだけ改造した。最終的にはほぼ全チーム通してたけど序盤全然とおらなくて焦った

C　これも意外とACが遅くて慌てた。難易度感覚壊れる。

D　原案。一捻りある2-SATを作りたかったんですがかなり思ったとおりになったっぽい？これも予想よりはるかに解かれず。。。直前に最大ケースが入ってないことに気づいて追加したらwriter解がMLEして制約が下がったりしてドタバタした。

E　この問題好き。tester解ちゃんと書いてないけど。

F　N頂点をK個の根付き木にする場合の数がケーリーの定理の一般化(?)で求まることに気づく以外のパートは簡単だと思っていた。テスター失格。

G　原案。こういう期待値計算好きだから流行ってほしい。

H　原案。UnionFind自体もマージテクが含まれるのでマージテクをマージテクする問題になっててなんか面白い気がした。テストケース生成が苦行だった。

I　数学。解説がかなり賢くてすごいなぁって言ってた。係数を全力で眺めると、

f(x) = a1*x+a2/2*x*(x-1)+a3/6*x*(x-1)*(x-2)+a4/24*x*(x-1)*(x-2)*(x-3)+...

のf(1)~f(N)を求めてくださいに帰着できて、僕はこの多項式を分割統治っぽくFFTで計算して代入するをして解いた。logが1個多いけど高速なNTTなら通る。

J　僕が通算9時間くらい考えて 2*奇数 のケースの構築を作ってそれをうまく倍々にしていく解法を生やしたらけんちょんに天才解説をされてキレた。グラフ理論でもうまく説明できるらしい。

 

解いてくださったみなさん、校正等でかなりお世話になったJAGのみなさん、本当にありがとうございました。

 

その後

東京の友達と久しぶりに会ったら地下アイドルのイベントに拉致された。イベント代は友達が出してくれたので絶対に自分は財布を開かない強い決意のもと臨んだら見事その場にいたアイドルにつられてチェキを撮ることになった。完。てんぷらはハニートラップに弱いんだよな、プーさんなので。

 

総括

コンテスタントとしては大反省(僕がまともならあと1問ずつ通っているので)、チームとしてはへのくんがやばい、writerとしては大満足、testerとしては難易度感覚さん。

いろいろと学びの多い合宿でした。ありがとうございました！！！！！