JAG 夏合宿 2023 参加記 - Todayのブログ

こんにちは。Today03 と申します。今回は JAG 夏合宿 2023 に参加したので、感想などを記していきたいと思います。

きっかけ

私は今年の ICPC 国内予選には出場しませんでした。これは、2027 年度の大学院卒業(予定)までの 3 年で 3 回出れるように参加権を残しておきたかったからです。

というわけでほぼすべての参加者がアジア地区予選への出場権を得ていると思われる中、ソロでの参加という形になりました。

私が今回の夏合宿に参加したのは、夏合宿の募集要項の対象者の項に

今年度の地区大会または来年度以降の ICPC に参加資格のある方すべて。

と記載されていたのが決め手でした。結果から言えば、参加して本当によかったです。

申し込み～当日まで

9/8 あたりまでに参加料を振り込むよう案内がありましたが、当然のごとく締切日の振込手数料がかからない時間帯ギリギリに振り込みました。。。

Day1 コンテスト前

開始日の午前に荷造りをしました。持ち物は以下の通りです。

PC
各種充電器
蟻本・PAST 本
筆記用具・A4 ルーズリーフ
クリップボード
2 泊分の着替え
歯ブラシ・歯磨き粉等
ポケット英和辞典
ライブラリ
iPad

持ってくればよかったもの

歯磨き用のコップ
スリッパ

持ってきたけど使わなかったもの

iPad

Day1 コンテスト

ソロ参加だったので即席でチームを組む必要があり、2 人で参加されていた香川高専のお二人 (take000 さん、misonikomipan さん) のチーム -O3 に入れてもらいました。

C++ を書ける take さんがメイン実装担当、私がサブ実装担当、misonikomipan さんが英語解読担当ということになりました。

Day1 は 2022 年の韓国の国内予選のセットでした。以下通した問題順に振り返ります。

A

いちばんの簡単枠 (?) でした。 take000 さんにささっと実装してもらってAC。

C

簡単枠 2 。ABC313-C と全く同じ問題です。これもささっと考察・実装を終えて AC 。

E

簡単枠 3 。最初問題文を誤読していて 1 ペナを出してしまいましたが、 misonikomipan さんが誤読に気づいてくれて何とか AC 。

G

簡単枠 4 。メモ化再帰すればいいだけだということに気づいて実装させてもらいました。最初メモ配列のサイズを見誤って RE しましたが、少し大きめに取り直すことで AC 。

K

最初はダイクストラみたいなことをすればよさそうという結論になりましたが、よく読むとグラフ 1 つにつき 1 辺以下しか移動できないので DP で OK 。これも take000 さんに実装してもらって AC 。

F

かなり通されていたので残り時間はこの問題に取り組んでいました。 SCC をしてトポロジカルソートした後 DP すればいいよねとなり、かわるがわる実装していましたが、どうしても RE ・ TLE がとれずコンテスト終了。

よく読み直すと各頂点の出次数が 1 以下とあるので、わざわざ SCC なんてする必要は全くなかったようです。。。

Day1 コンテスト後

夕食を取った後ルームメイトと顔合わせをしました。 sotanishy さん、 Kite_kuma さん、 sunrize さんのお三方がルームメイトでした。最初はかなり緊張していましたが、全員気さくで面白い方でした。よかったです。

顔合わせの後はすこし休んだ後 ABC にでました。部屋にいる全員が ABC に出ていたため程よい緊張感が流れており、これまでで一番集中できたと思います。時間ギリギリに F の黄 diff を通して Rating+82 、青が射程圏内に入りました。かなり嬉しかったです。

ABC 後は一人で風呂に入りに行き (他のメンバーは ABC 前にすましていました) 0 時に就寝しました。 ABC による興奮と普段と違う環境によりなかなか寝付けませんでした。

Day2 コンテスト前

7 時に起床。身支度→朝食→コンビニで昼食購入→コンテスト準備という流れでした。昼食はおにぎりを 4 つ購入しましたが、個人的にはこれがちょうどよかったです。

Day2 コンテスト

Japan Alumni Group Summer Camp 2023 Day 2 - yukicoder

C

幾何でした。解説では直径に着目するというとても賢い解法でしたが、私たちはそれに気づかず頑張って角度を計算したりしました。わざわざ fraction 構造体を定義してちまちま計算して AC 。 take さんと交代しながら実装しましたが、なかなか辛かったです。

K

$a→b→c$ の遷移ができないという条件の処理に困っていました。

各頂点について、累積コストと遷移元の頂点のペアの情報を保持しておけば、 DAG なので頂点を順番に見ていくことで DP ができます。あとは各頂点で次の遷移先をすべて探索し、 $a→b→c$ の条件に当てはまらないような遷移元にあたるまでコストの累積コストが小さい順に探索するという操作をすれば OK です。この探索は全体で高々合計 $O(K)$ 回でできることに気づき、方針を軽く説明して実装させてもらいました。

なんとか AC 。とても嬉しかったです。

これ以降は、順位表の状況的に A, H を中心に考察しようということになり、分担していました。

A

計算式をこねくり回しても何も見えてこずかなりつらかったのですが、実験コードを書いて実行してみると、 $f ( k ) = ( k - 1) ^ N$ になることに気づき、慌てて実装、 AC しました。最初から実験しておけばよかったです。

H

take000 さんが実験コードを書いてくれ、 $N$ に対して答えが 1 以上となるような $K$ は $O(\sqrt{N})$ でわかることは分かったのですが、それ以上は何もわかりませんでした。他のチームの話を聞いてみるとエスパーで通したところが多かったようです。 K より簡単想定らしく、信じられなかった。。。

B

misonikomipan さんがいい感じのところまで考察を進めてくれて、僕が misonikomipan さんの手足となって実装していました。出力デバッグをしまくってサンプルを合わせようと四苦八苦していたのですが、コンテスト終了。

Day2 コンテスト後

夕食、風呂を済ませて、ルームメイトと大富豪をしました。大富豪 streak 、 tourist 出しなどのおもしろワードが飛び出していました。楽しかったです。

そのあと ARC に出ましたが、普通に冷えました。悲しい。

Day3 コンテスト前

朝食が質素でした。

Day3 コンテスト

(yukicoder に追加されたらリンクを貼ります)

A, B

簡単枠ということで take000 さんと私でそれぞれ A, B を実装して AC しました。ある程度素早く通せてよかったです。

J

順位表の通され具合と、問題のテーマから J が解きやすそうだと個人的に判断し、ずっと一人で取り組んでいました。他のお二方にはその他の問題の考察をお任せしていました。

編集距離は前から決定していけるので、グリッドの全文字について、その文字が $T$ の何文字目にあたるかを全探索するような DP をすればよさそうという結論に至り

$dp _ {i , j , idx} = T の idx 文字目がグリッドの (i, j) の文字目になるときの編集距離の最小値$ のように DP テーブルを定義して実装しましたが WA 。色々なテストケースを試していると

2 2 
ab
dc
abxcd

で 2 と出力してしまっていることに気づき、修正。それぞれのマスで「待機」するような遷移があれば 1 にできますが、工夫しないと $O ( H W T ^ 2 )$ になります。 $ep _ {i, j, idx} = \min(dp _ {i, j, 0} + idx - 1, dp _ {i, j, 1} + idx - 2, ..., dp _ {i, j, idx - 1})$ を定義することで高速化して再度提出しますが、 WA 。

ランダムテストを書いてみると、

4 4 
xaxx
xbxx
xxcx
xxdx
abcd

で 2 と出力してしまうことに気づきました。どうやら各 $idx$ での更新が終わった時に自身の値と「他のマスの値+距離」を比較して DP テーブルを更新する必要がありそうです。最初は各 $idx$ でダイクストラをしましたが、最大ケースで 30 秒ほどかかってしまうことがわかり断念。よく考えると DP 値が左・下方向と右・上方向に伝播するように 2 重 for ループでの更新をそれぞれ 1 回ずつやればいいことに気づいて実装、提出しました。 AC 。