はじめに
2023年10月21日に、社内のメンバとチームを組んで PG BATTLE 2023 に参戦しました。この記事では、チームの構成、コンテスト中の取り組み方、個人およびチームの成績、などなど共有します。
PG BATTLE とは
PG BATTLEは、1チーム3名による企業・学校対抗プログラミングコンテストです。作品を提出して審査する方式ではなく、出題された問題を解くプログラムを90分間に4つ書いてオンライン提出するガチ勝負。
問題は「ましゅまろ」「せんべい」「かつおぶし」の3つのレベルに分けられており、事前にチーム内で、各レベルに担当者を割り振ります。「ましゅまろ」が一番簡単で、「かつおぶし」が一番難しいです。各レベル4問が用意されています。
各問題に点数が設定されており、コンテスト終了後の採点ですべてのテストケースに通ると、その点数を得ることができます。チームの合計点数によって順位が決まります。合計点が同じ場合は、解答時間の合計が少ないチームが上位となります。
企業の部では上位10チームが表彰の対象となるほか、キリのいい順位のチームに贈られる飛び賞も設定されており、上位入賞が厳しい場合でも楽しめるようになっています。上位3チームには賞金が贈られるほか、飛び賞チームには様々な賞品が贈られます。
コンテスト実施・解説・表彰式、すべてオンライン開催です。
通常の競技プログラミングコンテストとの違い
普段から AtCoder 等の競技プログラミングコンテストに参加している方は、PG BATTLE 特有のシステムに注意する必要があります。
| AtCoder 等 | PG BATTLE | |
|---|---|---|
| コンテスト開始・終了タイミング | ある時刻に一斉開始・一斉終了 | 13:00～14:40 の間の連続した最大90分、参加者ごとに開始し、提出ボタンを押すと終了 |
| チーム内での相談 | OK（チーム戦の場合） | NG |
| 役割分担 | 自由（チーム戦の場合） | 一人一つのレベルを担当、各担当4問 |
| 提出タイミング | 問題ごとに提出、時間内なら再提出可能 | 1問ごとに保存可能、4問まとめて1回のみ提出可能、再提出不可能 |
| 採点タイミング | ソースコード提出ごとに即座に採点（full-feedback 形式の場合） | コンテスト終了後に一斉に採点 |
| 順位付け | ①合計点数②チーム内で最後にACした時刻+ペナルティ | ①合計点数②各メンバの解答時間の合計 |
チーム戦ではありますが、コンテスト中の チーム内での相談は禁止 されています。競技プログラミングの一般的なチーム戦では、考察担当・実装担当といった役割分担を行うことが可能ですが、PG BATTLE では各メンバが1つのレベルを担当し、それぞれに問題を解きます。
ソースコードは一度提出したら再提出できず、コンテストが終了するまで正解したかどうかわかりません。システムテストを通らなかったからコードを直して再提出、という戦い方ができないため、制約やコーナーケースには特に注意が必要です。
また、合計点数が同じ場合は解答時間の合計が少ないチームが上位となるため、「時間内に解けない問題は諦めて早々に最終提出を行い、解答時間を短くする」という損切り戦略が有効になる場合があります。
余談ですが、PG BATTLE は TOPSIC というシステム上で開催されます。online-judge-tools/oj は TOPSIC に対応していない（2023年10月時点）ため、ローカルでのテスト実行は手動で行うなどして対処せねばなりません。
チームメンバの構成
PG BATTLE 参加経験のある2名に、PG BATTLE 初参加の筆者を加えた3名でチームを組みました。
AtCoder のレーティングは 青＋青＋水 という布陣です。レーティング順に担当レベルを割り当てたところ、私は「かつおぶし」を担当することになりました。
PG BATTLE 参加経験のあるメンバからアドバイスをもらい、事前に過去問を解いてみたり、コンテストで使う TOPSIC システムに慣れておいたりといった準備を行いました。
かつおぶし担当 問題ごとの取り組み方
かつおぶし担当の筆者はコンテスト中、順当に先頭から、難易度順に問題を解いていきました。昨年までとは異なり低難易度の問題に大きな点数が設定されたため、高難易度の問題から解く意味はあまりないと判断しました。
今回出題された問題は以下のページにて公開されています。
かつおぶし 難易度3 : 3 次方程式
高校数学Ⅲで習った中間値の定理ですね。方程式の左辺を $f(x)$ とおくと、$f(x)$ の符号が反転する箇所を二分探索すればよいです。
解答時間は5分程度（～13:05）でした。AtCoder 換算で茶色下位程度の問題という感触でした。
筆者は割とすぐ解けたのですが、コンテスト終了後の感想戦を見ると、苦戦した方も多くいらっしゃったようです。以下のような方針で解いた方も観測できましたが、微分する方針を選ぶと大変なようです。
- 相対誤差または絶対誤差が $10^{-5}$ 以下であればよく、精度があまり求められないので、区間 $[L, R]$ を線形探索（全探索）する
- 方程式 $f'(x)=0$ を解いて極大点・極小点で区間を分け、区間内で二分探索をして3個の解を列挙し、区間 $[L, R]$ に含まれる解を選ぶ
かつおぶし 難易度4 : 完全二分木の切断
完全二分木を切断してできる2つの木のうち片方は完全二分木になるので、$X=2^k-1$ あるいは $X=2^N-2^k$ を満たす正整数 $k$ があるとき、またその場合に限り、条件を満たす辺の選び方が存在します。
- $X=2^k-1$ 型のときは、2進表記すると $X=000\dots 0111\dots 1_{(2)}$ という形になっており、先頭に $0$ が $M$ 個連続しているとすると、$2^M$ 通りの辺の切断方法があります。
- $X=2^N-2^k$ 型のときは、2進表記すると $X=111\dots 1000\dots 0_{(2)}$ という形になっており、先頭に $1$ が $M$ 個連続しているとすると、$2^M$ 通りの辺の切断方法があります。
解答時間は17分程度（～13:22）でした。AtCoder 換算で緑色下位～茶色上位程度の問題という感触でした。
最終的な実装は簡単ですが、上記2パターンのうち後者に初めは気付かなかったこともあり、考察に少々時間を要しました。そのようなケースは入出力例にも含まれていないのですが、紙のノートに書き出して考察していたら気付くことができました。
かつおぶし 難易度5 : 部分列
$M\leq 100$ なので、空間 $\mathcal{O}(MN)$ の DP（動的計画法）を考えてみます。
DP テーブルを下記のように定義します。
-
dp[i][j]:= $i$ 番目までのうちいくつかを使って（$i$ 番目必須）、部分列$\bmod M = j$ となる場合の数
DP の遷移は下記のようにして $i, j$ が小さい方から更新することを考えます。
dp[i][j] \leftarrow \sum_{s=0}^{i-1} \sum_{t\in \lbrace x \mid (10x+S[i])\bmod M=j \rbrace } dp[s][t]
各 $j\in[0,M-1]$ に対して $(10x+d)\bmod M=j$ を満たす $x\in [0, M-1]$ および $d\in [0, 9]$ を前計算しておけば、DP は時間 $\mathcal{O}(MN^2)$ で解けます。$\sum_{i=0}^{n-1} dp[i][0]$ が答えです。
このままでは遷移が間に合わないので、遷移内の総和を高速に求められるようにします。$i$ については区間和の取得および値の1点更新が高速に行えればよいです。
筆者はコンテスト中、$dp[i][j]$ ではなく $dp[j][i]$ のように持ち方を変えて、各 $dp[j]$ を フェニック木 に乗せることで、区間和を高速に求められるようにしました。いわゆる「BIT 高速化」というテクニックです。この場合、時間・空間 $\mathcal{O}(MN\log N)$ で DP できます。
解答時間は20分程度（～13:42）でした。AtCoder 換算で水色下位～緑色上位程度の問題という感触でした。前計算を行ったり、フェニック木を DP テーブルに使ったりと、若干複雑なアルゴリズムになってしまったため、考察よりは実装に時間を要しました。
コンテスト終了後に気付いたのですが、実際には「BIT 高速化」を用いる必要はありません。DP テーブルを下記のように定義してみます。
-
dp2[i][j]:= $i$ 番目までのうちいくつかを使って（$i$ 番目を使わなくてもよい）、部分列$\bmod M = j$ となる場合の数
このように定義すると、$dp2[i][j] = \sum_{s=0}^{i} dp[s][j]$ であり、DP の遷移は
dp2[i][j] \leftarrow dp2[i-1][j] + \sum_{t\in \lbrace x \mid (10x+S[i])\bmod M=j \rbrace } dp2[i-1][t]
とできるので、時間・空間 $\mathcal{O}(MN)$ で DP できます。
かつおぶし 難易度6 : 二項数列
3問目まで解いた時点で約 58 分の残り時間があり、もしかしたら解けるかもと思ってしまったので時間を目一杯使って考察をしましたが、難易度6は時間内に解くことができませんでした。
愚直な DP を考えて高速化できないか、とか、$A_i$ の総和が $10^5$ 以下なので何かに使えないか、とか、二項係数の畳み込みは簡潔に書けるっぽいな、とか、コンテスト中に色々と考えてはいたのですが、力至らず。
解説放送を見たところ、まず愚直な DP を考えたのは悪くなかったようですが、そこから先の数学的気付きが足りなかったといえそうです。後で考察ノートを見直したら $\frac{1}{8}+\frac{1}{4}=\frac{3}{4}$ などと致命的な計算ミスをしており、これが無ければ二項係数の分布を合成したときの性質が見えていたかもしれません。
SNS での感想戦を観測したところ、どうやら AtCoder 黄色以上のレーティング保持者は概ね正解できており、解説されている解法とは異なり 形式的冪級数 を用いて解いた方が多いようでした。筆者はまだ1色分だけ実力が足りない、といったところでしょうか。
個人およびチームの成績
個人では 86分44秒/90分 で 80点/100点、企業の部かつおぶし担当で個人の部 34位/188チーム中 でした。
3問目まで22分しか使っていないので、この時点で4問目を諦めて最終提出していれば、個人の部かつおぶし担当15位だったのですが、あまり気にしても仕方がないでしょう。
チームとしては 114分41秒 で 220点/280点、企業の部 23位/187チーム中 でした。元々は飛び賞狙いで、真ん中くらいまで行ければ上等と思っていたので、かなりの善戦に驚きました。
あと1問、20点だけ多く得点できていれば10位入賞できていたので、かなり惜しいです。
来年の PG BATTLE に向けての抱負
飛び賞は逃しましたが、健闘できたこともあり、楽しく参加できました。精進しつつ何回か続けて参戦すれば、10位入賞も不可能ではないと感じました。
筆者は今回が初出場でしたが、おぼろげながら順位の相場もわかってきました。企業の部については、AtCoder レーティング基準で 黄＋青＋水 のような布陣なら入賞が狙えそうです。筆者はもう3年以上青色帯で停滞しているのですが、できれば来年までに暖色コーダーにランクアップして、万全の態勢で次回の PG BATTLE に臨みたいところです。
We Are Hiring!