Asa's Website

JAG 夏合宿 2023 参加記

jagcompetitive programmingparticipation log

作成日 / 最終更新日

Table of Contents
参加登録Day 1家出る前渋谷観光コンテスト 1 (韓国国内予選セット)夕食部屋に移動ABC320Day 2コンテスト 2 (有志セット)ARC165Day 3コンテスト 3 (JAG スタッフセット)帰還まとめ？

JAG 夏合宿 2023 に参加してきたので参加記です！

参加登録

ICPC2023 は 悲しい結果になってしまった けど、夏合宿は ICPC に参加資格のある人は誰でもおっけーらしい。
これ絶対たのしいやつやん！で参加登録をした

これみんな予選突破してる人なんだろうなぁ、突破できずに参加して申し訳ありません... になってたけど、全然そんなことなかった。

Day 1

家出る前

忘れ物ないよな... ヨシ！ Twitter や！
そういえば CodinGame Summer Challenge 2023 の結果がでてるっぽいな、見てみるか...

2 桁だった、うれしい！

渋谷観光

ちょっと早めにでて時間があったので、渋谷観光をした。

前日になんか Splatoon 3 のポップアップイベント をやっていることを知り、行ってみた。

そして当日になって ポケモンのイベントも渋谷でやってるよ！ ということを知り、どうせ渋谷に来たんだし... ということで行ってみた。
行ってみたらわかったんですが、この 2 つはめちゃくちゃ近くでやってた... (徒歩 30 秒くらい)

そして渋谷駅発のバスに乗って、いざ会場のオリセンへ...

12 時集合なのに 11 時半に着いてしまったので、オリセン内の食堂で昼食をとった。
食券を買って並んだ。サラダバーやデザートバー、ドリンクバーがあって、お得感を感じた。
(後に朝夕食もこの食堂でとることに気づく)

コンテスト 1 (韓国国内予選セット)

チーム決めがあって助かった...
レートの昇順に貪欲にとってく感じでチームを組んだ結果、 漁師さん と おここさん と組むことに。
みんな青。がんばるぞー！

チーム名は、それぞれの ICPC2023 のチーム名の一部から。
自分が「Maximum-executive」、漁師さんが「nowcovv」、おここさんが「elephant_ spaghetti」だったので。

ぞい！

まずは読む。おここさんが前、自分が真ん中、漁師さんが後ろから読む感じで。
A がわかったというので実装してもらい、 13 分で AC。
実装してもらっている間に E を読んでいて、解けたのでその後実装。
適当に累積和とって、貪欲。 18 分で AC。
次は C が簡単そうだったのでみんなで考え、まあ平均とればいいよねという結論に。
ここも実装してもらい、 34 分で AC。

この時点で 3 位くらいにいた気がする。
次に K, F, G, J を解いた。 (ここら辺は詳しく覚えてない)

一応 F を実装したので書いておくと、適当にループ判定して適当にメモ化しただけ。
Runtime Error の表示が。
テストしてみると、 N=0N = 0 のケースでおかしいっぽい。
えー！？ 厄介すぎませんか？
何を出力すればいいんだ... になって clar を投げてしまった......
「N = 0 のときってどうなってますか？制約上あり得ますよね？ (英語)」 → 「山がないことを表します。 (英語)」 それはそう

J は漁師さんが平方分割でガチャしてた。
TLE して、分割の境界を変えて、みたいなことをやってたらなんか通ったっぽい。

結果、 7 完で 4 位に！ (！？)
チームみんなで「上振れしすぎ～！」になってました

夕食

混みすぎ！ チームメンバーで一緒に食べた。

部屋に移動

泊まる部屋に行く。
部屋は 4 人部屋。 Sakasu さん、 しょぼんさん、 nok0 さん と一緒に寝ることに。
nok0 さんは Maximum-Cup 2023 のネームプレートをつけてきていただいていて、作ってよかった～になりました (ありがとうございます)

色々話したりお風呂入ったりして時間経過

ABC320

Wi-Fi 環境が悪すぎ + いろいろ環境が違すぎるので Unrated で参加。

結局 Wi-Fi が遅すぎてテザリングしてしまった...
あまりよくない結果になってしまった...
そしてテザリング切るの忘れていて、 1 か月のデータ量制限 3 GB を 1 日で使い切ってしまった... (そんなことある？)(その後課金して + 1 GB を獲得...)

Asa
Asa
@a01sa01to
·Follow

#ABC320 おつかれさまでした～ A: C++ めんどくさいので Python でやった B: ぜんぶやる C: 誤読しまくった (2 ペナ)、候補をあげまくる D: ただのグラフだった、 BFS E: RE！？ローカルで通ってるけど → queue の empty 判定... WA！？ → priority_queue... AC F: まあメモ化じゃ通らないよね...

2
Reply
Read more on Twitter

Day 1 終了、おやすみなさい～

Day 2

コンテスト 2 (有志セット)

朝起きて朝食食べてしばらくすると、コンテスト 2 の時間に。
今回もチーム分けをすることになり、今回は おここさん と まーたさん と組むことに。漁師さんは別のチームへ。

これ、レート昇順に組んだら昨日とまったく同じチームになるんじゃね！？になってたんですが、ちゃんと考慮されてました。

今回もチーム名はそれぞれのチーム名「masamune」「Maximum-executive」「elephant_ spaghetti」から。

ぞい！

まずは一通り読んでみる。
C が解かれていそうだったので、とりあえず C を見る。
サンプルからエスパーすると、奇数なら 0 、偶数なら N(N−2)2\dfrac{N (N - 2)}{2} になりそう？
実装したら AC。その後まーたさんが証明してくれた。嘘じゃなくてよかった。

次に解かれていそうだったのが A だったので見てみる。いろいろ式変形したり、実験して書き出したりしてみると、 f(k)=(k+1)Nf(k) = (k + 1)^N になりそう。これを足し合わせればいいので、実装してみたら通った。またまーたさんが証明してくれた。ありがたい。

H を見てみる。うーん、これは bit 全探索して実験してみるか...ということになり、とりあえず書いてみる。
いろいろやってみると、おここさんが規則性に気づいた。
NN を固定してみると、 KK としてあり得る数が決まる。そしてあり得る KK の xx 番目は K=(N−x+1)xK = (N - x + 1) x (ただし xx は 0-indexed) になってそう。さらに、基本的に、値は二項係数 (N+1x)\dbinom{N + 1}{x} に対応してそう。例外は N mod 2=1N \bmod 2 = 1 かつ x=N+12x = \dfrac{N + 1}{2} のとき (記憶が正しければ)、 (Nx−1)\dbinom{N}{x - 1} っぽい。
この式を変形していくと xx の値がわかり、 KK があり得る値かどうか判定できる。
AC！よかった～

K をやる。
いったん自分が実装してみることになったが、なんかうまくいかない...
実装を交代してもらうと、おここさんがサンプル通ったというので投げてもらうと TLE してしまい、どっか高速化したら通った (記憶が正しければ)。

その後 B, F を考えてみるも、解けず。
結果、 4 完の 12 位。 エスパーの勝利した回だった (?)

ARC165

夕食を食べてお風呂入って ARC ぞい！
部屋に帰ってすぐにスピードテストしてみると 2.2 Mbps くらい出てたのに、 ARC 直前には 2.1 KBps に... これ絶対建物内にいる競プロ er のせいだろ になってました。 Wi-Fi 弱すぎ！

結局今回も Unrated 参加。
結果論だけど、全然よくなかったので Unrated でよかった。

結果を見てみると、 ICPC や Maximum-Cup 2023 などでお世話になっている m_99 先輩が入赤してた！？ すごすぎ！ おめでたい！ 🎉🎉

Asa
Asa
@a01sa01to
·Follow

#ARC165 おつかれさまでした～ A: 素因数が 1 個しかなければ No (何を思ったか素因数 1 個でも指数が 3 以上ならいけると考えてた、なんで？) B: 前から順番に見ていって位置関係ができるだけ変わらないようにするのがうれしい → 詰めが甘い C: 決め打ちにぶたん → 詰めが甘い

3
Reply
Read more on Twitter

Day 3

コンテスト 3 (JAG スタッフセット)

もう最終日か...
今日もチーム分けしたんですが、人数が 3 の倍数ではなかったのでいろいろ話し合ったところ、初日と同じく漁師さん、おここさんと組むことに。
チーム名も初日と同じ。

ぞい！
まず A を担当。これはやるだけだったのでやった。
B は漁師さんとおここさんが考察、おここさんが実装を担当。少し詰まったらしいが、なんとか通してくれた。
実装していただいている間にほかの問題を読んだり、 C の考察をしたりしていた。

C は漁師さんが解けそう...！とのことだったので、ほかの問題を考えていた。
J を見てみると、 DP で解けそう。でも実装めんどくね！？ になったので、 DP をそのままグラフに落とし込み、 01-BFS で実装した。
計算量が不安だったけど、通った。よかった～
すかさず C が解けたらしいので漁師さんに実装してもらい、通った！

E, I が解かれていたので考えていたが、間に合わず...。
結果的に正解の考えも、詰めが甘くて反例あって違うな...になってしまっていた。かなしい。
E は確率ではなく数え上げに帰着してしまい、階乗を埋め込むチームになっていた。
それでも間に合わなかったので、何を思ったか「コンパイル時間は実行時間制限に含まれますか？」と clar を投げたら「このドキュメントを見ろ (全体公開)」という返事が返ってきて、晒し者にされてしまった...
最後はもうヤケ食いしてた。

帰還

コンテストが終わり、解説も終わったあと、交流をしようかなーと考えていたが、出ていけっぽい雰囲気があった + 荷物が多すぎたので、帰ることに。
新宿駅まで漁師さんと一緒に帰った。
そこからもう荷物持ちながら 1 時間近く立ちたくねぇ～になってしまったので、グリーン車に乗って帰った。ホリデー料金で安くなってた。勝利。

まとめ？

運営のみなさん + 交流していただいたみなさん、ありがとうございました！
3 日で (AtCoder も含めると) 16 時間 40 分もコンテストやる機会なんてそうそうないし、強い人と長時間入れる機会もないので、とても貴重な経験ができたと思います。
かなりボリューミーで、とても充実した 3 日間でした。
時間があっという間に過ぎてしまっていた...

ありがとうございました～！
来年強くなってまた参加したいです！
誰でもウェルカムな感じだったので、 (選考が行われない範囲で) 人数が増えるとうれしいな～～