ICPC 2024 国内予選参加記

はじめに

kureha といいます。AtCoder 黄色です。橙が見えてきてほしいのですが、8 月末まで Rated が 3 回くらいしかなさそうで、まだまだ道のりは遠そうです。今回は ICPC 2024 国内予選の参加記です。

チーム紹介

チーム名 : kotamanegi_hint_kureya

メンバー 1 : shinchan
諸々担当

メンバー 2 : Daylight
色々担当

メンバー 3 : hint908
なにかしら担当
shinchan曰く「自分と Daylight は安定タイプで、908 は天才タイプ」、別チームの強い人曰く「一発型」らしい。（ほんまか？）

コンテスト前

プリンターが三台あってどれにするかを決めたり、Y.Y. 先生が問題作ってるならマトロイドとか DM 分解とかか...? とか言ったりしつつ時間をつぶす。

ちなみに RAINBOU の Twitter (現 X) に投稿されているチーム揃ったよのポスト、こたまねぎの世界って書いてあるけど直前までこたまねぎ〇〇でした。

コンテスト開始

だいたい時系列順に書きます。提出履歴とかどこかで見れたりしませんかね...?

コンテスト開始直後は事前の取り決めにより（印刷ボタンを押した後） Daylight が A を見ます。
実装中は画面半分使って shinchan が B を見るとか言ってた気がするけど結局見てたのだろうか。
なお印刷待ちで確実に暇な方がおひとり。

[02:33] A : Daylight

shinchan が B を見て実装します。
A を通したくらいか少し前に問題が一セット届いたので D を見て、Daylight に C を渡します。

[08:33] B : shinchan

Daylight にパソコンが渡され、shinchan は E へ。

D、簡単だけど書くの面倒だなぁと思いつつ細部を詰めます。
過去問を使った練習ではペナを生やしまくっていたので、そうならないように紙に疑似コードを書いていました。

[18:31] C : Daylight

パソコンを渡され、D を実装します。
Daylight は F を見に行ったはず。

疑似コード、役にはたったがまあまあ雑でした。
途中で Segmentation Fault を吐いたけど原因は容易に特定でき、特に詰まることもなく実装完了し提出。

[28:04] D : hint908

模擬国内のときは CD で詰まったのですが、本番はここまで予定通りに進みました。
ここからは高度な柔軟性を維持しつつなんとやらというやつです。

shinchan は E を解けてなくて考察中、Daylight が見ていた F は手を動かしながら考えたいタイプの問題だったようなので Daylight にパソコンを渡します。
自分は E~G のどれを解くかでしたが shinchan の指示で E を一緒に考えることに。

長さ $N$ の正整数列 $c$ に対して条件を満たす $N \times N$ 行列があれば構築する問題でした。
$c_1 = c_n$ の場合は自明なのでよくて、 $c_1 \neq c_n$ の場合は裏側からも見ることを考えると $c_1 \dots c_n \dots c_1 \dots c_n$ ならよさそうという提案をする。
色々手で解いたりしていけそうという結論になったので実装は任され shinchan は G へ。
ただ $c_1 \dots c_nc_1 \dots c_n$ のケースしか手で解いていなかったことに気づいたがどうにでもなったのでパソコンが空くのを待ちながら疑似コードを書き書き。

F がバグったのかペナったのかは忘れたけど交代し、3 行しか書かれていない疑似コードを装飾しながら実装。
軽実装なのはわかっていたので疑似コードが書けた段階でパソコンを奪った方がよかったのかもしれない。
$n \leq 3$ のときは全探索するかとか shinchan と話し合ってたけど面倒だったので書かなくてもいいかという相談。
サンプルにないケースも合ってそうだったので、全探索なしでいいよということになり提出。

[1:14:57] E : hint908 + shinchan

一発 AC やったぜ。

Daylight にパソコンを渡し、shinchan の指示で H へ。
英語混じりのクソ長問題文と入出力説明を読み終わったくらいで G の助太刀を頼まれます。

また構築かよと思いながら見ます。
E は数列 → $N \times N$ 行列でしたが G は数列 → 2 つの数列でした。

総和が偶数でないといけないのは自明で、偶数である要素は半分にすればよさそうな感じに見えるのはそう。
問題は奇数をどう分ければいいかで、これは偶数が１つでもあればこうやればいけそうという提案をする。

納得してもらえたので自分は H を考えて、２人は交代しながら実装。
いろいろ考えると最短経路問題になりそうで、ABC あたりに似たような問題があった気がした。
$(1, (N+1)/2)$ から $(N, (N+1)/2)$ へ行くことができなくするにはどう障害物を置けばいいかみたいなやつ。
明らかに実装が面倒とか思っていると G が WA った。
コードを見てみるとあら不思議、奇数しかない場合が No 固定ではありませんか。
自分はここを偶数が１つでもある場合と同じように実装すると Y/N が判定できると思っていて、shinchan は偶数が１つでもあれば存在すれば Yes、それ以外なら No と思っていたらしい。
これについては言うのを忘れていて (= No だと思われるのは当然の話で) 、要反省ポイントでした。
とりあえず $s = (1, 1)$ なら $a = (0,1), b=(1,0)$ でいいことを伝えて考察しなおし。