PG BATTLE 2021に参加しました

December 20, 2021

これはMobility Technologies (MoT) アドベントカレンダー20日目の記事です。

2021/10/23 に開催された企業・学校対抗のアルゴリズムコンテストPG BATTLE 2021 にMoTから参加したので、今回出題された問題や結果、感想についてまとめます。

PG BATTLE とは？

PG BATTLEとは2018年から毎年開催されている企業・学校対抗のプログラミングコンテストです。問題が与えられ、制限時間内にできるだけ速く、できるだけ多くの問題を解く（与えられた問題を解くプログラムを実装し提出する）ことで順位が決まる、いわゆる「競技プログラミング」といわれる形式のコンテストになっています。3人1組でチームを組みますが、本番では3人それぞれが「ましゅまろ」、「せんべい」、「かつおぶし」という異なる難易度の問題に相談なしで個別に取り組む、という少し独自の（囲碁や将棋に近い？）チーム戦になります。

今回、MoTからはチーム「カニキ」として参加しました。参加メンバーと分担は

「ましゅまろ」木村勇仁
「せんべい」二瓶泰徳
「かつおぶし」亀澤諒亮

でした。これから、それぞれの参加メンバーから出題された問題や感想について書いていきます。

ちなみにチーム名のカニキはチームメンバーの名前を１文字ずつ取って決めました。

ましゅまろ

ましゅまろを担当した木村です。今回初めてPG BATTLEに参加することになり、結果は4問中2問正解という結果になりました。今回はPG BATTLEに参加したきっかけ、どんな勉強したか、当日どんな問題を解いていたかを紹介します。

参加したきっかけ

MoT社内ではSlack上での雑談が盛んで、その中の雑談チャンネルの1つである競技プログラミングというチャンネルに入社3日目あたりで参加させていただきました。ある時、亀澤さんが雑談上で PG BATTLE があるから参加しませんか？という募集をされていたので、とりあえずやってみよう！というのがきっかけで参加しました。

本番前にどんな勉強をしたか

問題難易度の傾向として競技プログラミングコンテストAtCoderを例にすると、亀澤さん曰く難易度 400 ~ 1200 ぐらいを解けるようになっていった方がいいということで毎週1時間程度集まりAtCoder Problemsを使ってAtCoderの過去問を解きながら勉強していきました。

本番当日どんな問題を解いていったか

1. 難易度１「物理現象グラフィックバトル」(PDF、解説動画)

高さY cmの円柱のうちK/X cmが水面より下にある時、水面より上にある部分は何cmか？

どんな風に考えたか

文章読んだのですが、文章からだと何を求めたいのかよくわからなかったので、図を書き起こしました。
図に対し問題文から与えられている情報を入れ込こみ、どうやったら回答を出せるか計算式を色々書き起こしました。

感想

文章を読んでから、図に書き起こすまでの動作が遅かったので悩んだらすぐに手を動かすのが大事です。

2. 難易度３「ゼロのない整数」(PDF、解説動画)

X以上の整数のうち、全ての桁に0が含まれない最小の整数は何か？（ただし、 $X≤10^{100000}$ ）

どんな風に考えたか

1回目
- 与えられた数値から最小となる数値を絞り込んで結果を出す。
2回目
- 1回目のケースだと桁数が多いものだと時間がかかりすぎるため修正
- 数値桁を桁数が大きいところから見ていき、0が見つかったところから全て1にする処理に変更した。

感想

最初はこちらの問題を解く時に間違えた考えをしていました。0 をなくせばいいので範囲を絞り込んで最終的には0が含まれない数値になれば良いと考えていましたが、その場合だと桁数が多くなってくると計算量が多くなってしまい、TLE（Time Limit Exceeded、実行時間制限超過）になるところでした。気づいたきっかけは、桁数が多かった場合にTLEになりそうという経験則からきたものだったと思います。

3. 難易度３「一点封鎖」(PDF、解説動画)

格子上の二点間を格子に沿って最短距離で移動する時、指定した座標を経由せずに目的地に到着するパターンは何通りあるか？

感想

この時点で残り時間が10分程度になっていたので、この問題を解くことより解いてきた問題が本当に正しいのかを確認する時間に当てていました。AtCoder等とは違いコンテスト中に正解かどうか分からないので、後で後悔する方はどちらかを考えた結果、残り時間は見直しをする時間にしました。

PG BATTLE 参加を通しての全体的な感想

今回初めてPG BATTLEに参加し、普段のAtCoderのコンテストより緊張しました。より早く提出することも大事なのですが、今回はより正確なコードを提出するよう心がけました。おかげでなんとか2問解くことができましたが、他の人たちに比べるとまだまだなレベルだと感じるのでAtCoderコンテストへの参加を通して、来年参加するときには3問解けれるようになっていればと思います。また、今回このPG BATTLE初参加でも亀澤さんと二瓶さんが誘ってくれたことに感謝しております。来年参加するときはせんべいを担当できるぐらいの実力を目指していきます。

せんべい

せんべいを担当した二瓶です。競技プログラミングはまだまだ初心者で、気が向いたらAtCoderに参加してみる、くらいの温度感でマイペースに楽しんでます。

結果は4問中2問正解でした。個人的には3問正解を目標としていたので、少し残念な結果となってしまいました。

大会参加全般の感想ですが、今回初めてチームでの競プロコンテストに参加しました。チーム戦といっても、チーム間での問題共有は禁止されているため、大会自体の進め方はAtCoderなどのコンペと変わらない印象でした。ただ、大会前にチームメンバーで模擬コンテストを何回か実施ししており、そのような練習方法は新鮮で楽しかったです。競プロは1人で黙々と問題に取り組む時間が長くなるので、このような大会を一つの目標とすると、モチベーションを失わず競プロを長く楽しめるかもしれません。

以下、各問題の概要と解いてみた所感です。3、4問目に関しては解答することができなかったため、詳細は公式ページの解説動画等を参照いただければと思います。

1. 難易度2「7番勝負」（PDF、解説動画）

確率 $P$ パーセントで勝てる勝負を7回行った場合に勝ち越す確率を求めよ。

制約

$P$ は整数
$0 ≤ P ≤ 100$

以下、 $P$ を少数表記で考えます。

各勝負回数ごとの勝敗パターンの確率(e.g. 2回目の場合、2勝0敗は $P^2$ 、1勝1敗は $2P(1-P)$ 、0勝2敗は $(1-P)^2$ )を順次求めていき、7回後に4勝以上のパターンの確率を足し合わせれば求めることができます。

感想

シンプルな問題で上記解法を素直に実装すれば解ける問題でした。

2. 難易度3「連結成分数の見積もり」（PDF、解説動画）

以下の問題が $T$ 個与えられる:

N頂点M辺からなる多重辺や自己辺のない無向グラフについて、連結成分の個数として有り得る最小値と最大値を求めよ。

制約

$1 ≤ T ≤ 10^5$
$1 ≤ N ≤ 10^9$
$0 ≤ M ≤ N(N-1)/2$

まず最小値を求めます。実際に紙に描いてみると分かるのですが、以下の2パターンに分けて計算することができます。

$N > M$ の場合 : $N-M$
$N ≤ M$ の場合 : $1$

まとめると、 $\max(N-M, 1)$ で計算できます。

次に最大値を求めます。この場合、 $M$ 個の辺を最小の頂点数 $K$ で使い切り、残り $N-K$ 個の頂点は連結しない形でグラフを構築すれば、連結成分を最大にでき、答えは $N-K+1$ となります。例えば $N=5、M=3$ の場合、3つの頂点で3本全ての辺を使い切ることができ、答えは $5-3+1=3$ になります。

$K$ 個の頂点で消費できる辺の最大数は $K(K-1)/2$ なので、 $M ≤ K(K-1)/2$ となる最小の $K$ を求めればいい事になります。

$T$ の取りうる最大値が $10^5$ と大きいので、計算時間を制限内に収めるために、 $K$ の算出には2分探索を使う必要があります。

感想

最小値・最大値ともに、実際紙に描いてみるとなんとなく解答が分かるような問題でした。最大値の場合は計算時間削減のために2分探索を使う発想に行き着けるかが重要だったかなと思います。私はこの発想がなかなか思い付かず、解くのにかなりの時間を使ってしまいました。

3. 難易度4「トーナメント表」（PDF、解説動画）

$2^N$ 人がトーナメント形式で勝負し、 $i$ 番目の人の順位が $a_{i}$ となった。トーナメントの人の並び方としてあり得るものを1つ出力せよ。

制約

$1 ≤ N ≤ 16$
$1 ≤ a_{i} ≤ 2^N \;(1≤i≤N)$
$a_{i}\;(1≤i≤N)$ は2の累乗である

4. 難易度6「[リ[[スー]バ][ズパ]ル]」（PDF、解説動画）

$1, 2, ..., N$ がランダムに配置された数列Aと、M個の区間 $[A_{i}, B_{i}] \;(1≤i≤M)$ が与えられる。M個の区間から一つ選び、区間内の数列を反転させる操作を0回以上繰り返し、辞書順最小となるAを求めよ。

制約

$1 ≤ N ≤ 2\times10^5$
$1 ≤ M ≤ 2\times10^5$
$1 ≤ A_{i} ≤ B_{i} ≤ N$
すべての $i\;(1≤i≤M)$ について $(A_{i}, B_{i}) \neq (1, N)$
すべての $i, j\;(1≤i, j≤M, i \neq j)$ について $(A_{i}, B_{i}) \neq (A_{j}, B_{j})$
すべての相違なるM個の区間は互いに交差しない
入力は全て整数である

かつおぶし

かつおぶしを担当した亀澤です。PG BATTLEに参加するのは今年で3回目になります。今回は二瓶さん、木村さん、自分の3人で参加しました。（実は毎年違うメンバーで参加しています。）私がslack上の競技プログラミング雑談チャンネルで参加者を募集したところ、この二人が手をあげてくれました。参加してくれた二人には感謝しています。

私は学生自体から競技プログラミングをしていて、ちょうどPG BATTLEの前後はAtCoderのレートが青から黄色（レートに関する詳細はこちら）になるかならないかという時期で、かなりのめりこんでやっていました。それで肝心の今回の結果はというと、4問中1問正解という苦しい結果でした。普段のAtCoderでのコンテスト形式と異なり、コンテスト終了時まで提出したプログラムが正しいかどうか分からないという、かなり正確性が要求されるコンテスト仕様に見事にハマりました。後ほど各問題については振り返りますが、コンテスト中は3問は解けたと思っていたものの、そのうち2問はコーナーケースで不正解になっていました。事前に提出回数一回という制限でバーチャルコンテスト（過去問を元に仮想的にコンテストを作成できる練習用のツール）で練習していたものの、本番ではその成果が出ず残念でした。

以下、各問題の解説と振り返りになります（Rust実装のソースコードはこちら）。この難易度は正直、競技プログラミング未経験者にとってはかなりハードルが高く、解説も問題に合わせた難易度としているため、特に後半はかなり前提知識を要するものになっています。数式も多用するので苦手な方は雰囲気だけ感じつつ、最後の感想まで読み飛ばしていただければと思います。

1. 難易度３「階乗の桁数」（PDF、解説動画）

$N!$ を10進表記したときの桁数を求めよ。ただし、 $N!$ の最上位桁は2以上8以下とする。

制約

$1 ≤ N ≤ 5 \times 10^5$

コンテスト中に正答できたのはこの一問だけでした。（泣）

これは「logを知っていますか？」という問題になります。

\log N! = \sum_{n=1}^N \log n

となることを利用すれば、底が10の場合の値の小数点以下を切り捨てて1を足したものが答えになります。浮動小数点数で計算する場合、誤差が気になりますが、最上位桁が2以上8以下という制約のおかげであまり気にせず計算しても大丈夫なようです。

2. 難易度４「桁と数列」（PDF、解説動画）

正の整数 $S$ と数列 $D=(d_1, ..., d_N)$ が与えられる。次の二つの条件を満たす数列 $A=(a_1,...,a_N)$ を出力せよ。そのような数列が存在しない場合、-1を出力せよ。

$a_1 + \cdots + a_N = S$
$a_i$ を10進表記した場合の桁数が $d_i$

制約

$1 ≤ N ≤ 100$
$1 ≤ S ≤ 10^9$
$1 ≤ d_i ≤ 9$

この問題はコーナーケースによって不正解でした。まずは簡単に問題の解説をします。

「 $a_i$ を10進表記した場合の桁数が $d_i$ 」ということから $10^{d_i-1} ≤ a_i ≤ 10^{d_i} -1$ と言い換えることができ、Aが存在する必要条件を導くことができます。

\sum_{i=1}^N 10^{d_i-1} \le S \le \sum_{i=1}^N (10^{d_i}-1)

Sがこの条件を満たさない場合、条件を満たす数列Aは存在しません。逆にこの条件が満たされた場合、目的のAを構成することができます。これは $a_N$ について次を満たすように取ることができることから帰納的に構築できます。

\sum_{i=1}^{N-1} 10^{d_i-1} \le S-a_N \le \sum_{i=1}^{N-1} (10^{d_i}-1)

具体的には $f(n) = \sum_{i=1}^{n} 10^{d_i-1}, g(n) = \sum_{i=1}^{n} (10^{d_i} - 1)$ として、

\max(S - g(N-1), 10^{d_N-1}) \le a_N \le \min(S -f(N-1), 10^{d_N}-1)

を満たすように（例えば下限を取るなどで） $a_N$ を計算すればよいです。あとは再帰的に $i=1,...,N$ について $a_i$ を求めることができます。

感想改めて自分のコンテスト時の解答を見ると最初の必要条件の上限を誤って $(\sum_{i=1}^{N}10^{d_i}) -1$ としていたようです。今見ると明らかなバグですが、与えられたサンプルケースではこれでも通ってしまっていたため、最後まで気づきませんでした。この問題ではサンプルケースが少数かつ自明なケースしか与えられていなかったので相当注意深く実装、テストする必要がありました。条件ギリギリの境界付近のテストケースを自分で作ってテストしておけば気がつけたので、かなり悔しいミスでした。

3. 難易度６「ペアなすごろく」（PDF、解説動画）

数列 $R=(R_1, ..., R_N)$ と変数 $x=1$ に対して、 $x≤N$ を満たす間、以下の操作を繰り返す。

$1 ≤ p ≤ q ≤ R_x$ を満たす整数組 $(p, q)$ を一様ランダムに一つ選び、その $p$ を $x$ に加算する。

操作終了後の $x$ の期待値を求めよ。

制約

$1 ≤N≤2\times 10^5$
$1≤R_i≤2\times 10^5$

この問題もサンプルケースは通ったものの不正解でした。まずは簡単に解説をします。

期待値の問題では終了状態から考えると見通しがよくなることが多いです。今回の問題の場合、終了状態では必ず $x>N$ となっているので、操作終了時に $x$ だった場合、それがそのまま期待値になります。次に $x≤N$ の場合を考えてみると、操作途中に $x$ だった場合、その次の値としては $x+1, x+2, ..., x+R_x$ の $R_x$ 通りが考えられます。ただそれらの値に遷移する確率は一様ではなく、 $x+p$ に遷移する確率は $\frac{2(R_x-p+1)}{R_x(R_x+1)}$ となります。これは各 $p$ について取りうる $q$ の値の個数を調べることで得られます。ここで遷移という言葉を使ったため、知っている人は気づくと思いますが、これは動的計画法（Dynamic Programming, DP）を使います。 $\textrm{dp}(x)$ を値が $x$ からスタートした場合の操作終了時の値の期待値とすると具体的な漸化式は次のようになります。

\textrm{dp}(x)=\begin{cases} \sum_{p=1}^{R_x} \frac{2(R_x-p+1)}{R_x(R_x+1)}\textrm{dp}(x+p) &\text{if } x \le N \\ x &\text{otherwise} \end{cases}

このDPに沿って $x$ の値が大きい順に埋めていき、 $\rm{dp}(1)$ がこの問題の答えになります。ただ、このままでは計算量が $O((N+\max(R_i))\max(R_i))$ となってしまうため、高速化が必要になります。漸化式をよく見ると累積和のような構造が現れることに着目すると次のような変形ができます( $x≤N$ の場合のみ考えます）。

\begin{aligned} \textrm{dp}(x)&=\sum_{y=x+1}^{R_x+x}\frac{2(R_x-y+x+1)}{R_x(R_x+1)}\textrm{dp}(y)\\ &=\frac{2(R_x+x+1)}{R_x(R_x+1)}\sum_{y=x+1}^{R_x+x}\textrm{dp}(y)-\frac{2}{R_x(R_x+1)}\sum_{y=x+1}^{R_x+x} y\textrm{dp}(y) \end{aligned}

よって、 $M=\max(x+R_x)$ , $\textrm{DP}_0(x) = \sum_{y=x}^{M}\textrm{dp}(y)$ , $\textrm{DP}_1 (x)=\sum_{y=x}^M y\textrm{dp}(y)$ とすると、遷移が $O(1)$ でできるようになるため、全体として $O(N+\max(R_i))$ となり、実行時間に間に合います。

感想自分のコンテスト中の解答では、ここまでの考察はできていたものの上の $M$ の上限（DPテーブルの大きさの最大値）として制約未満のものを設定していたために、大きな制約のテストケースに対して実行時エラーを起こしてしまっていました。二問目とは異なるタイプのミスですが、これも制約が最大となるようなテストケースを試していれば気付けていた間違いでした。これも大いに反省すべき点です。

4. 難易度６「コイン投げ」（PDF、解説動画）

"H"と"T"からなる文字列 $S$ が与えられ、"H"(表)と"T"(裏)が等確率で出るコインを、次の条件を満たすまで投げ続ける。

最後に出た $|S|$ 回の結果が $S$ と一致

条件を満たすまでにコインを投げた回数を求めよ。

制約

$1≤|S|≤10^6$

これはコンテスト中に解法に辿り着くことができませんでした。考え方のキーワードとしては、「確率遷移グラフ」「KMP法」あたりなのかな、と思います。

まず、コインを投げ続けて最後の $k$ 文字が $S$ の先頭 $k$ 文字と一致する場合を考えます。この状態からコインを投げて、次も $S$ と一致した場合、 $S$ の先頭 $k+1$ 文字が一致した状態となります。一方そうではない場合、 $S$ の先頭 $j(≤k)$ 文字が一致した状態になります。例えば、S=HTHの場合を考えるとSの先頭1文字が一致している場合（コインを投げて最後に"H"が出た場合）、次に"T"が出ると、"HT"となり、Sの先頭2文字が一致している状態になり、もしくは"H"が出ると"HH"となり、その最後の1文字がSの先頭1文字に一致している状態になります。このような遷移をグラフとして表現すると以下のようになります。

上のグラフで緑の状態からスタートして初めてオレンジの状態に到達するまでの移動回数の期待値が求めるものになります。グラフの形状としては、 $k(<|S|)$ 文字一致している状態からは必ず $k+1$ と $j(≤k)$ の状態への遷移があるような形になっています。ここで動的計画法（DP）を使うことを考えます。DPの状態を $k$ として $\textrm{dp}(k)$ を「初期状態からスタートして初めて $k$ の状態に到達するまでに必要な移動回数の期待値」とするようなDPを考えると、漸化式は以下のようになります。

\textrm{dp}(k+1) = \textrm{dp}(k) + \sum_{i=1}^\infty \frac{(\textrm{dp}(k) - \textrm{dp}(j)+1)(i-1) + 1}{2^i}

この漸化式を詳しく説明すると、前半の $\textrm{dp}(k)$ は初めて状態 $k$ に到達するまでの移動回数の期待値、 $\frac{(\textrm{dp}(k)-\textrm{dp}(j)+1)(i-1)+1}{2^i}$ は $i$ 回状態 $k$ に到達した後に初めて $k+1$ に到達する場合の期待値になります。期待値の線形性によりこれらを分けて足し合わせることが可能になります。上の式には無限級数が出てきますが、これは解析的に計算が可能で整理すると以下のようになります。

\textrm{dp}(k+1) = 2\textrm{dp}(k) - \textrm{dp}(j)+2

このDPを $\textrm{dp}(0)=0$ を初期状態として小さい順に埋めていき、 $\textrm{dp}(|S|)$ が答えとなります。

あとは各状態 $k$ から遷移する状態 $j$ が分かれば良いことになります。しかし、ナイーブに各状態から遷移可能な状態 $j$ を求めようとすると $O(|S|^2)$ かかることになり、この制約だと間に合いません。従って高速化を考える必要があります。求めたいものは $S$ の各先頭文字列 $S_{:j} \; (j=1,...,|S|)$ について、その $k$ 文字以降の接尾文字列に $S_{j+1}$ とは異なる文字 $t$ を連結した $S_{k:j}t$ の中で $S$ の先頭に一致する最大の $k$ ということになり、これはKMP法と呼ばれるアルゴリズムを利用することで効率的に計算できます。

感想個人的にはループが存在するような確率遷移グラフを扱う問題は苦手です。まだまだ確率的な直感が働かず立式にかなり時間がかかってしまいます。一方でこのような問題は割と頻出するイメージもあるので典型問題の一つとして身につけておくべきだと思います。またKMP法を含む文字列アルゴリズムについても知識があやふやなところがあり、一度ちゃんと勉強した方が良いなと思っています（思い続けて数年経っているような…）。全完を目指すとなるとこれくらいの範囲の知識は身についてないと難しいことを実感しました。実装してみるとハマるポイントはあるものの実装量自体は大したことはなく、全体として今年の問題セットの特徴として実装は軽めな印象でした。

参加しての感想とMoTにおける競技プログラミングとの関わりについて

今回でPG BATTLEには3回目の参加になりますが、毎年自分がメンバーを集めて、毎回自分が「かつおぶし」難易度を解いています。ただ、今回は初めて一問しか解けないという経験をしてまだまだ自分は競技プログラマとしては未熟なんだな、ということを改めて思い知らされました。普段の業務では、人と何かを競って技術を磨く、という経験はなかなかする機会がないため、競技プログラミングを通して自分の立ち位置を知り、上を目指すという感覚を持てることは非常に刺激になっていると思います。もし来年以降も開催されるなら、次こそは全完を目指したいところです。

MoT社内の競技プログラミングコミュニティは、そこまで規模は大きくないまでも、slackチャンネルを中心に存在しています。PG BATTLEのようなイベントへの参加だったり、普段のコンテストの感想を言い合ったりなどゆったりと活動しています。業務との関わりについては、一口にエンジニアといってもかなりの業種がMoT社内にあるため、どの業務でも競技プログラミング的な能力が直結するとは言い難いですが、アルゴリズム的な能力が必要とされる場面は多く、競技プログラマが活躍できる機会もある会社なのではないかと思います。このブログでもアルゴリズムが生きた事例は紹介されているのでご覧いただければ幸いです。

最後に、明日のMobility Technologies アドベントカレンダー21日目は谷村亮介さんによる「MoT出向半年間の振り返り」です。お楽しみに！

We're Hiring!

📢

Mobility Technologies ではともに働くエンジニア（あわよくば競技プログラマ）を募集しています。

興味のある方は採用ページも見ていただけると嬉しいです。

Twitter @mot_techtalk のフォローもよろしくお願いします！