ICPC 2022 国内予選に shuz*, nope, ruthen で shichifuku として参加しました。
このチームは 3 年目となります。
本番前
チーム練習は 6 月中旬から、サークル活動で AOJ-ICPC の問題を解きました。
模擬国内予選 2022 の成績は以下になります。
参加資格のあるチームの中では 27 位、選抜チームの中では 23 位でした。
大学内 2 位でしたが、本番なら通過できる順位だったので、この調子で頑張りたいという感じでした。
今年は大学から 5 チーム出場する予定であり、1 チーム実力が飛び抜けているチーム (otagai_tasukeai) があるため、その他 4 チームによる 2 位争いになると思っていました。
本番
大学の計算機室に集合しました。
コンビニに行ったり、チームメイトやコーチや他のチームの方々と話しているうちに、気づけば開始 10 分前になっていました。
nope が A を、ruthen が B を、shuz* が C を読むと決めていました。
昨年一昨年とは異なり、アクセス集中による開始時刻の延長などはないまま始まりました。
問題は下記リンクから参照できます。
B
開始後まず B を読みます。取る手札が決まっているババ抜きのようなゲームのシミュレーションを行う問題でした。
問題文中にゲームが必ず終了するということが書かれていたため、まだ手札が残っている人の id を std::set で管理し、最後に手札を引いた人の id を管理しながら実際にシミュレーションする方針で実装することにしました。
やや実装に苦戦しましたが、無事 AC しました。割と早かったと思います。
B に取り組んでいるうちに nope が A を AC していたため、C に向かいます。
C
shuz* が読んで、実装しています。サンプルが合わないと言っていたので、「これ k 日続いていたらスコアは k^2 ですね」みたいなことを言ったような言ってないような……で気づいたら AC していました。
この時点では全体で 15 位以内に入っており (うろ覚え) 、かなり好調なスタートだったと思います。
3 人で一通り問題に目を通し、その時まだ D 以降が全く解かれていませんでしたが、割とすぐに D の AC が出たこともあり、D を考えることにしました。
D
順列 s が与えられるので、連続部分列に区切り、各列の先頭のうち最も小さい番号から順に入場していくような操作を行い、入場順が順列 t と一致するような区切り方は何通りあるかという問題でした。
順列に対する数え上げの問題なので、挿入 DP などを考えますが、うまく状態をまとめることができず、詰まります。s を区切った後のそれぞれの部分列は t 中の (連続するとは限らない) 部分列になることはわかりましたが、それ以上が進みません。
必要条件から考えることにしました。まず列 t の各要素を前から見ていくことで、「ここで必ず分割しなければならない」ような場所が決まります。例えば sample 1 では
s = [4 2 3 5 1]
t = [1 3 4 2 5]
ですが、この場合、[4 2][3 5][1] が必要条件になることがわかります。
このように分割した後、実際に操作を行って t にならなかったら答えは 0 通りです。(sample 3 や sample 5 がそれに対応します。)
実際にはさらに [3 5] を分割してもよく、よってこの場合は 2 通りとなります。
さらに分割できる部分列とそうでない部分列の違いが良くわからず、そもそも必要条件で区切った後、各部分列を独立に考えても良いのかさえ怪しいため、難航します。
各部分列について、それまでに出てきた要素の最大値より大きい値の直前では切ることができます。最大値未満の場合は絶対に切れません。そして、この切れる位置が実は任意に選ぶことができ、十分条件になっているのではないかという話になります。(←ここまで詰められていたかは怪しいです。)
shuz* がこれらの条件などをもとに実装を進めますが、ペナルティが出ます。
自分も実装して比較したほうが良いのではないかと考え、開始 1 時間半以上経過しているところで実装を開始します。(今思えば、この判断をもっと早く行うべきでした……。)
この時点で otagai_tasukeai は 4 完しており、学内 1 位通過は厳しそうという雰囲気になります。
それどころか TX Rapid も negi_mo_tabero も Team ITF. も 3 完しており、D を早く解かなければ……と焦ります。
実装とデバッグに 40 分程度かかり、テストケースの実行も 1 ケース 1 秒程度要しましたが、shuz* のテストケース 1 の実行結果と異なることもあり、とりあえず投げてみるとなんと AC します。
そのままテストケース 2 も通ります。この時点で 2 時間 20 分が経過。
2 ペナしていましたが、ほかのチームよりも 3 完までが早く、かつほかのチームもペナルティを出していたため、ここから 2 問通されない限り、学内 2 位にはなりそうという雰囲気になりました。
その後は AC 数を見ながら E と F に挑戦します。
E
もともと D を考えているときに時々 E に浮気しており、条件は括弧列に言い換えられることはわかりましたが、そこから進みません。
判定だけでもできないか、ということになり、各要素の割り当てを決めると、整数計画問題に帰着できそうですが、条件式が多すぎて厳しそうです。
結局よくわかりませんでした。
F
構文解析パートはほぼおまけのようなものではありますが、考察パートがわかりません。貪欲に置き換えていけないのかと言ったところ、shuz* からすぐに反例が飛んできます。
結局これもわかりませんでした。otagai_tasukeai は終了直前に通しており、地力の差を感じました。
本番後
結果は 36 位で、例年の感じだと通りそうでしたが、東大が 10 位以内に集中していることもあり、怪しい気持ちになってきます。(東大強いな～となりました。)
そして JAG の方が作成した拡張機能で判定したところ、予選敗退でした……。
当日はあと 805 秒早ければ通過していたと思っており、10 分以上の差があるなら仕方ないと思っていました。
しかしこの記事を書いているときに気づいたのですが、実は合計で 140 秒早ければ通過していたようです……。
その後はほかのチームの人たちと集まって問題の解説などを行いました。
普段のサークル活動よりも人が集まっていて楽しかったです。
ご時世など諸々の事情を考慮し、打ち上げなどは特にせず、チームメイトを車で駅などに送り届け、帰宅しました。
以下反省などです。
対面で集まったこと、チームとしては 3 年目ということなどもあり、意思疎通はできていたと思います。コンテスト中も個人的にはリラックスした雰囲気で臨めました。これはずっと同じチームでやってきたためだと思います。
結果論ですが、D を迷わずに実装し始められたかが勝負の分かれ目になってしまいました。ですが自分の実力ではすぐに正当性を証明することはできなかったので、あと少しに見えて大きい壁だったのかなと思います。あるいは高難度を通す力が足りなかったと言えるかもしれません。
しかし、初動がかなりうまくいったのは個人的にはかなり評価ポイントでした。nope は A を、shuz* は C を素早く通してくれました。自分も普段 B を炎上させてしまいがちなので、成長を感じられました。
そもそも順位で見れば過去最高なのはかなり嬉しいです。
最後になりますが、大会運営に関わったすべての皆様、ありがとうございました。
特にチームメイトの 2 人にはとてもお世話になりました。ありがとうございました。
また何か機会があったらよろしくお願いします。
