feature image

2024年7月6日 | ブログ記事

ICPC2024 国内予選 参加記 (Oxojo 視点)

初めまして. 24B の Oxojo と申します.

ICPC2024 国内予選に参加しました. Yokohama には行けませんでしたが, 一応参加記を書きます.

メンバー

traP の方で組んでもらい, 24B 3 人のチームになりました.

いろいろと試した気はしますが, 現時点ではロールの割り当てはこれが一番上手くいくな, ということで早めにチームの方針を決めていました.

本番までにやったこと

traP の algo 班の方で, 何回かチーム練習会を企画されていたので, そちらに参加しました. 基本的には全員集まって参加できました. これに加え, 主に私が声をかけて, だいたい 4-5 回ほどチームで練習をした記憶があります.

最初の早解きパートは私が担当するのは元から決定していました. 何回か練習する中で, 初動は非常に安定していたので, 主に中盤~終盤の考察を切り替える判断を鍛えたり, チームの連携力を高めたりすることに重点をおいて練習をしていました. その結果, 特に本番の数日前の練習では, 考察のスピードが上がっていたり, 時間の無駄遣いが減ったりと, 練習の効果が出ていると感じられることが多かった印象です.

最初は他の 2 人の今の実力をあまり知らなかったので, どのぐらいの位置につけるかは分からなかったですが, チーム練を重ねていくにつれてなんか行けそうな雰囲気になってきて, 私は本番でうまく噛み合えば Yokohama 進出も狙えるのではと思っていました. そのため, 私個人の中では Yokohama 進出を今年の目標に定めることにしました.

競技中の動き

実装はすべて Oxojo が担当しているため, 名前は省略.

A

左から順に足すだけだな, と考えながら実装をし, ペナなしで通す. (00:02:11)

B

赤い人がリードしているか, 青い人がリードしているかの状態が変わる瞬間をカウントすればよいとおもい実装. 並走している状態を考えておらず, 少しだけタイムロス. サンプル時点で気づけたおかげで, ペナを発生させずに通すことができた.(00:06:22)

C

どこかで見たことある... と思いながら実装を始める. このタイミングで, romophic が「D の実装・方できた」と, 方針と簡潔な実装を書いた紙を私に渡した.

特殊な index の動きに少し苦労したものの, 本質的には BFS を書くだけ. ここも確実にペナなしで通せた. (00:12:59)

D

romophic から簡単な方針を聞いた後, 実装を始めた. とりあえずサンプルを試してみるも, なぜか全く違う座標を示してしまう. この辺のタイミングで, giagia が E 問題の方針をある程度思いついていたので, バグっているコードを印刷して romophic にデバッグしてもらう.

E

giagia から説明を聞いて, 少しずつ実装をする. 最初の場合分けが終わったタイミングで, romophic が「デバッグできた」と言った. giagia はまだ E の解法が正しいかわからん, と言っていたので, とりあえず E の考察を続けてもらい, D をまずは通すことにした.

D

デバッグしてもらったコードを見ながら修正. なぜか無限ループが発生して抜けられず, romophic と 2 人でコードを睨む時間が続いた. 後で romophic が「座標の更新ができていないです」みたいな指摘をしてくれたので修正. その後もちょこちょこ修正し, 無事サンプルが合ったので提出, AC を得る. (01:09:24)

E

giagia が「これで絶対あってる」というぐらいに解法を詰めてくれたので, その説明を聞きながらコードをかく. サンプルが合うので提出するが, 1 ペナ. とりあえず giagia の考えてくれたテストケースを試してみると, 見事にバグっている. 修正して, 正しいことを確認して提出したものの, デバッグ用の出力を消し忘れてしまい追加でペナを出してしまう. 慌てて出力を消して提出し, なんとか AC. (01:27:14)

F

D や E の実装であたふたしている間に, 2 人が F の解法を考えてくれたので説明を聞く. 「斜めだから添え字が面倒そう」->「45° 回転するか?」と提案し 45° 回転を考えてみるも, うまく実装ができず, 結局回転せずにやる方向で決定.

言ってもらった方針を元に実装し, サンプルを試すも, 3 番目で 3 を出力. 困ったよ~とヘルプを投げる. コードを印刷して説明していたところで, 1 回見た球の打つ方向が右上でない場合はシミュレーションを打ち切るという部分の条件分岐をしていなかったことに気づき, 修正. 3 番目で No が出たものの, 今度は 2 番目でも No が出てしまった.

シミュレーションをして, 球が存在してそれの打つ方向が右上じゃなかったら打ち切るという方針だったが, 最初に見つけた球の打つ方向が右上じゃなかったとしても, 次に同じ球を見つけた時の打つ方向が右上になる可能性があるとわかり, 条件をつけ足すことに. ただ, 試行錯誤を重ねても, 3 番目で 3 を出力するときと, 2 番目で No を出力するときを交互に繰り返す. 結局バグを取ることができず, 競技終了.

G

E や F を実装している間に, 他の 2 人で G の考察をしていた. romophic が, マッチング問題に近いのではと提案したため, 2 人でグラフでの解法を考えていたらしいが, 上手く考察が進まず, 結局時間がないため 6 完を優先していこうということで F のデバッグに回ることになった. (この辺の動きは把握してなかったので後で giagia が教えてくれた)

結果


全体 32 位, 学内 6 位でした. Yokohama 進出はなりませんでした.

(2024/07/08 追記) 公式結果(https://icpc.iisf.or.jp/2024-yokohama/domestic/icpc-2024-result/)が発表されて, 上位 35 位以内に入ったため表彰対象です!やった~

感想

競技が終わってみると, 結構いいところまで行けたな, と思いつつ, ここまで行けるなら Yokohama 行きたかったなととても悔しい気持ちになりました. その後 3 人で夕食を食べたり, 適当にだべったりしていて, 久しぶりにチーム戦楽しいな, と感じました. ただ, 復習をすると, 自分がもう少しこう実装すればよかったなとか, ここに気づいて提案したかったなとか, 反省点はボロボロ出てきます.

来年はもうこんなに悔しい思いはしたくないので, もっと強くなります.

Oxojo icon
この記事を書いた人
Oxojo

24B Algo

この記事をシェア

このエントリーをはてなブックマークに追加
共有
記事一覧 タグ一覧 Google アナリティクスについて 特定商取引法に基づく表記