PG BATTLE 2023 に参加した
PG BATTLE 2023 に参加した。
PG BATTLE は個人ではなく所属企業や学校からチーム単位で参加する。1 チームは 3 人。出題される問題は合計 12 問で、それが 4 問ずつ 3 つの種別に分類されている。事前に種別ごとに担当者を申請して固定するので、1 人 4 問を解くことになる。チーム参加ではあるが個人戦を前提としていて、1 つの種別を複数人で回答することは認められていない。
自分は「せんべい」という中難度の種別を担当した。
準備
3 年前に AtCoder でのコンテストに参加して以来の競技プログラミングで、言語を含めて全てを忘れていた。流石にそのままの状態で参加しても面白くないしチームにも申し訳ないので、復習をすることにした。
言語は 3 年前も C++ を使っていたので今回も C++ を使うことにした。
復習は標準入出力、全探索、bit 全探索、二分探索、累積和、貪欲法などをやった。3 年前にある程度身についていたものだけを選び、DFS, BFS, Union Find, DP など学習中で定着してなかった分野は復習対象から除外した。もし出題されたら潔く捨てることになる。
環境構築を始めたのがコンテストの 1 か月前ぐらいで、それから週 5 日ぐらいは問題を解くようにしていた。
最終的には diff 500 ぐらいの問題が解けることもある状態になり、思ったより良い結果が出せそうな気がしていた（フラグ）
具体的な目標としては担当する 4 問の中で、1~2 問は正答しようと思っていた。3,4 問目は無理。
当日
1 問目は（実はギリギリでミスに気付いて）正答できたが、2 問目に苦しんだ。
種別や難易度によらず、PG BATTLE 全体に言えることだが、AtCoder の ABC よりは数学がテーマになっていることが多い。2 問目はまさに数学で、確率と期待値の線形性に関する問題だった。
競プロで期待値を扱う問題自体が初見だったので、まず問題を正確に理解するのに時間がかかった。
実装方針は愚直にやると 3^(10^5) を扱う必要があり、絶対にオーバーフローすると分かっていたが、愚直に計算する以外の方法を検討できなかった。
3 文字ずつで期待値計算できたらいいんだけどな、と思いつつ数学的に確証（確信）を持てなくてやらなかった。こういう場面で、愚直にやって駄目なんだからとりあえず出題者の意図に近そうな実装をしてしまう、という選択を取れなかったのはコンテストの参加者としては判断ミスだった。
「コンテストの参加者としては」というのは、それが常に判断ミスと言えるかというとそうではないとも思っているからだ。実際の問題解決の場面で、数学的に自明でないのにとりあえず出来そうな実装をする、という行動は取れない。仮に正しい答えを出すコードが書けていたとしても他人に説明できず自分自身もなぜ正しいのか理解できないのでは問題を解決したとは言えない。
より本質的な敗因は、問題を分割して扱うことが正しいと判断できなかった数学力の不足だと思う。期待値の線形性と言ってしまうのは簡単だが、本当に 3 文字ずつに分割して加算するだけで良いのか？文字列全体の ABC の数が期待値なのに？そのときの確率は 3 文字分の中だけで考えていいのか？例えばその 3 文字以降に ABC が存在したらそれは加算しなくて問題ないのか？重複カウントはないと言えるのか？など考えていくと、本番時の自分は「何か怪しい」と思ってしまった。
2 問目の解説動画で直大さんが「ちょっと難しかったかも」と言っていたので、それなりにせんべい担当者は苦労したのかもしれない。
所感
振り返ってみると、約 1 ヶ月間に学習した内容は全然出題されなかった。むしろ 10 年以上前に学習した高校数学の確率と期待値に関する理解度を問われるという事態で、何だかコンテストが終わってもやり切った感が薄かった。それなりに準備して挑んだだけに、理不尽な感じがする。PG BATTLE は 2 年分の過去問も解いたのだが、AtCoder の ABC と微妙に雰囲気が違っていて対策が難しい。結局できることは AtCoder の過去問を中心とした演習になってしまう。今更高校数学まで復習しようという気持ちにはならない。PG BATTLE も普通に ABC と同じ傾向の出題でも良いと思うんだが...
ただ、ブランクがあるとはいえ高校数学はそれなりに勉強した過去はあるわけで、悔しさはある。何となく自己肯定感は下がったが、逆に社会人として謙虚な気持ちにもなった。算数・数学的思考については 3 年前に AtCoder をやっていたときも苦手だと感じることが多かった。人には向き不向きがあるんだろうと思う。
試験の辛み
こういう話をしていると、高校 3 年の大学受験の頃を思い出す。どれだけ必死に準備してきても何が出題されるかは分からないし、予想もしないような出題やケアレスミスで得点につながらないことも多かった。
なんでこんなに頑張っているのに成績が伸びないのか、と模擬試験の後に鬱々として寝込んだ日もあった。まさに筆記試験の厳しさだが、村上春樹さん風に言うと”神経症的ゲーム”だったとも言えると思う。
もちろん、出題されなかった範囲でも学習したこと自体は無駄ではない。しかし、解けた・解けなかったという事実だけが得点に反映され、他者と比較され、順位や偏差値として評価される。これは特殊なルールのゲームに過ぎないと思う。実際の（特に現代の）社会でこのゲームが得意なことにそこまで意味があるとはあまり思えない。本当に、当時はよく 1 年間も受験生やってたよなぁ。
まとめ
結果はともかく、PG BATTLE がきっかけで、C++ と基本的なアルゴリズムの復習の機会にはなった。数理的な問題を解くときの頭の使い方も普段の生活や仕事ではしないので、良い刺激になった。AC できたときの嬉しさも久しぶりに味わった。
一方で、準備しても十分には報われるとは限らないという試験の厳しさを思い出すこともできた。自分の向き不向きについても再認識できた。
そういうわけで、自分は競プロよりも別のことに時間を使った方が幸せになれると思っているので引退状態のままでいるつもりだが、また来年誘われたら期間限定で競プロをやることはあるかもしれない。もっと簡単な準備だけして、数学ゲーだと割り切って気軽に参加する方が楽しめそう。