hogecoder

つたじろう(Tsuta_J) 競技プログラミングの記録

JAG 夏合宿 2019 参加記

JAG 夏合宿 2019 に参加しました。昨年に続いて二回目で、今年も four-t としてチーム全員で参加しました。今回は作問もすることになったので昨年とは少し違う面持ちで参加した気がします。

Day 1

割と時間ギリギリでオリセンに向かっていると、知ってる顔のひとたちも同タイミングでたくさん向かっていたので一緒に歩く。

去年と部屋違ってビックリ、部屋おおきい。

いろいろとコンテスト前のアナウンスがあったのち、準備してコンテスト開始。

最近は自分が A を解く担当をしているので A をやる。よめない (は?) もたもたしてるとえび君が B 解けたらしいので代わると通る。FA。プロか?

チームメイトと A を確認していたらいろいろ解釈がまちがっていたことがわかる。介護をうけて AC。

C はペナ出しながらもわりと早い段階で通ってよかった。

これ以降で最初に読んだのは E だった気がする。わりと考えた。

TAB 君によると D が解けたらしいので話を聞くと中国剰余定理が必要らしい。中国剰余定理は持ってるので写経する。一応 __int128 を使いながら実装して通った。

えび君がやっていた J 問題の話を聞くと、最小化は二部グラフの最大マッチングやればできそうという話になり、これも持ってるので写経する。通った。

その後 E の解法を TAB 君がひらめいて、重み付き UnionFind が必要というという話になって、これも持っているので写経しようとしたが、持つ値がヤバそう。これ Python でやったらよくない?となって、えび君に Python に移植してもらった。再帰が多くて RE しているようだったがそれも最終的には回避して AC。この辺チーム戦ならでは感があった。

あとはだいぶ冷えていて、2 問おしかった

  • I: 誤差死
  • K: FFT の工夫がたりなかった

この辺詰められるようになりたいね

終わった後はご飯と風呂を済ませて、Day3 の準備とかボドゲとかやってた気がする。たのしかった。

Day 2

この日も自分が A を解いた。WA (は?) 冷静になる時間が必要なので代わる。

えび君が E を AC。最初の一問担当、代わったほうが良くない・・・?

冷静になったので A を AC した。

F をかなり考えるがわからない。このグラフ上で最大独立集合すればできるんだけどな〜、無理だな〜、で終わってしまった

TAB 君と自分が F を考えている間に I がいつのまにかえび君によって通されていた。FA らしい。やったじゃん。でもそのすぐ後にジャッジ解の間違いによるリジャッジのアナウンスがあった。結果的に FA は幻となった。かなしいね。

D が無限に通されてるわりにわからんとなるが、流石におかしいので問題をよく読む。解釈を間違えていて、正しい解釈をすると書くべきコードが分かったので書く。通った。

中盤何してたのかおぼえてないんですが多分ずっと F やってた。

最後の方に J を考える。全員でなんとか考えると数式が生えて、さらにこれはラグランジュ補間があればどうにかなりそうなことがわかる。これは持っているので写経する。でも最後の詰めが甘くて、偶奇によって標本を変えないといけないことを失念していて人生終了した。この辺は実力が如実に現れたという感じがしますね・・・。

懇親会があってカツサンドくんを撮ったりおしゃべりをしたり翌日の Writer として紹介されたり哀愁ただようカツサンドくんを撮ったりした。

この日にあった ABC で黄色になった (5 回目)。ボーダー芸人を安定させるんじゃなくて黄色を安定させてほしい。

Day 3

Writer なのでコンテスト前にいろいろアナウンスした。この日のコンテスト時間は 4 時間でした。

A は偶奇でなにかやりたいなと思ったのと、簡単枠が枯渇していたので作りました。A 問題なので本質部分はとても軽く、注意力のほうが重要だったかもしれません。

B はそもそも原案が生えた時点で (合宿に限らず) コンテストに出すかどうかすら迷いました。相談したら、いいんじゃない?とのことだったので置きました。逆から処理するとわりと破滅すると思いますが、実は楽が出来ます。

あとテスターをちょこちょこやりました。個人的にヤバい問題だと思うのは F, G, I, J あたりで、この辺は概ね想定通りの結果となりました・・・。

HUPC が終わって問題が余っていたときに声をかけてくれた not さん、JAG のセットを作るためにたくさん作業してくれた Writer の皆さん、英語の校正や連絡面などでたくさんサポートしてくださった JAG スタッフの皆さん、本当にありがとうございました。当日は特にトラブルなく終わって本当に良かったです。

なお、Day3 の解説は Google ドライブ に上げたので、復習にお役立てください。そのうち JAG の Wiki にも載る、はずです。

以下個人的メモ

持ってないもの

  • 一般グラフ最大マッチング
  • 重み付き UnionFind (や、持ってるんだけど久しぶりすぎて中身がどうなってるか曖昧だったのが非常に良くないし改変しづらそうだったからなんとかする)
  • CHT (や、持ってるけど 復習してない問題 があることに気づいてしまった )

復習するもの

ぜんぶ

その他

疲れをとる (明後日から会津合宿マジ?????)

総括

学びしかなかったです、行って本当に良かったです。会津も行く人はまたよろしくお願いします!