PG BATTLE 2022に参加しました
こんにちは、フジクジラ🐋（ナビゲーション向け測位技術開発担当）・見習いスパルタ人２号（地点検索システム開発担当）・co-yarn（経路検索エンジン開発担当）です。
この度、この3人でチームを組み、PG BATTLE 2022という学校・企業対抗のプログラミングコンテストに参加し、企業の部6位（190チーム中）に入賞することができました！
この記事では、コンテスト当日の様子や出場してみての感想などを主にお伝えしたいと思います（主に競技プログラミングをやったことのある方・興味のある方向けの内容になります）
PG BATTLE 2022とは
PG BATTLE 2022とは、企業・学校対抗のチーム戦の競技プログラミングコンテストです。
同じ学校や企業に所属する3人でチームを組み参加します。
大まかなルールは以下の通りです。
「ましゅまろ」「せんべい」「かつおぶし」の3つの難易度の問題セットがある
チーム3人で一つずつ担当
各問題セットは4問からなる
ましゅまろが最も易しく、かつおぶしが最も難しい
提出は4問一括で1回限り
コンテストが終了してから正解/不正解が分かるシステム
チーム3人の合計点数の大きい順で順位が決まる
1人100点満点、3人合計で300点満点
同点の場合は3人の提出時間合計の短い順
チーム内での相談は禁止（将棋の団体戦に近いイメージ）
オンラインで行われるので、好きな場所からの参加可能
ナビタイムジャパンでは、今回参加した3人で、第1回のPG BATTLE 2018から毎年参加しています。2018年当時、社内で競プロ部という活動があり、その一部メンバーで集って参加しました（※競プロ部はコロナ禍になってから活動休止中）。
第1回では、運も手伝って2位に入賞することができました。しかし、その後の第2回以降は一度も3位以内に入賞することができていません。そのため、再び3位以内に入賞することが私たちの目標でした。
参加メンバーは3人とも普段からAtCoderというオンラインコンテストサイトで研鑽を積んでいます。
PG BATTLEは年に一度、日頃の成果を試す場でもありました。
当日は、一箇所に集まったりはせず、それぞれ自宅から参加し、コンテスト終了前後にslackで注意点や結果などをやり取りしていました。
以下、各メンバーの参加記です。
※実際の問題とその解答例・解説が公式サイトに掲載されています。競技プログラミング経験のある方・興味のある方はぜひ考えてみてください。以下、一部の問題の解法に対する言及を含みます
テスト不足に泣いたましゅまろ
ましゅまろ担当のco-yarnです。業務では経路検索エンジンの運用・研究開発をしています。
AtCoderのコンテストにはほぼ毎週参加しており、レーティングは1700前後(青色) です。
業務ではC++を使っていますが、競技プログラミングではC++を触るよりも前から使用してなじんでいたPython(Pypy3) を使っています。実行速度の面では他の言語と比べて不利なことが多く気をつける点が多いですが、比較的コードを短く書くことができることや、イテレーターに対して便利なライブラリがあったりと有利な側面もあって気に入っています。余談ですが、実行速度が求められるヒューリスティックコンテストではPythonは使用せず、勉強も兼ねてRustを使用しています。
本番前の意気込み
昨年に引き続いて一番簡単なましゅまろ担当なので、満点は狙いつつなるべく速く解くことを意識していました。具体的には、30分で解き終わることを目標にしていました。また、あえてチーム戦であることは意識せず、自分のベストを出すことに集中して臨んでいました。
当日の様子
1問目は競技プログラミングを始めたばかりの人向けの問題だと感じました。制約から先頭が ”090” 以外のケースなど特殊なケースがないことを確かめて解答しました。
2問目でいきなりつまずいてしまいました。一見単純に見えるので前から順に処理を行っていけばよさそうにみえました。しかし、この方針で実装しようとすると今計算している値とこれまで計算した結果を覚えておく必要があり、さらに記号を起点にして処理を行っているとうまく末端部分を処理する必要がありました。このような複雑な処理はコードも長くなってしまい、非常にバグを生みやすいコードになってしまいます。いくつか自分でもテストケースを作りながら念入りに確認を行いました。実際バグがいくつか見つかり、修正に時間をかけてしまうことになりました。ほぼ修正が終わったタイミングで、より簡単な解法を思いついてしまいました。ここで書き直すかどうかかなり悩みました。簡単な解法だとおそらく数行程度で書くことができバグの心配も少ないが、書き直すことに時間を使ってしまう。一方で今のコードだとある程度バグがないことが確認できたがバグのリスクが高いことに不安が残るーー最終的にはテストケースを追加で確認し、そのままのコードで解答することにしました。
時間を使ってしまったことに少し焦りを感じながら進んだ3問目は、単純な順位を表示する問題に見えました。しかし、同点が存在することを考慮する必要がありました。2問目の反省を踏まえて簡単に書けるロジックがないかしばらく考察したのですが、思いつかず。直前の点数を覚えておきながら順位を操作する単純な解法で答えることにしました。こちらもバグりやすい処理だと思い、追加でテストをいくつか行って解答しました。ここまでで20分かかっており、目標の30分を目指すには厳しい時間になっていました。
4問目は、制約が小さく単純な動的計画法でできないかと最初は考察していました。10本ある足をどちらか1方にいくつ渡すかで場合分けすることで11通りに圧縮でき、蟹味噌を含めて1杯ずつどちらに渡すか決めていけば間に合うのではと考えていました。しかし実際にコードを書いて N = 8 の最大ケースを試してみると間に合いませんでした。それもそのはず、実はこの考え方でも22^8(≒5×10^10)通りの分け方があり、制限時間に間に合いません（一般的に、10^8の計算量で1秒程度かかります）。具体的な計算量を実装前に見積もっていなかった点は反省点です……。ここで目標時間の30分を超えてしまい焦りが募っていました。その後、最大ケースの半分の N = 4 なら通り数が 22^4(≒2×10^5)通りしかないことに気が付き、半分全列挙による解法に思い至りました。N = 1のコーナーケースに注意しながら実装し、サンプルで正解することを確認しました。Pythonでは思いがけないところで定数倍での制限時間オーバーをすることがあるので、念のためもう一度最大ケースで制限時間をオーバーしないことを確認して一安心していました。最後に解答が保存できていることを確認し、最終的には40分で提出しました。
終わってみての感想
コンテスト終了後の結果は、4問目が不正解で70点……。見返してみると、ケアレスミスで間違った答えになってしまうケースがありました。テストケースの乏しさに若干の不安を覚えてはいたのですが、テストケースの自作方法がパッと思いつかず、確認を怠ってしまったのが完全にあだとなりました（奇しくもかつおぶし担当のフジクジラ🐋さんとは色々な点で対照的な結果になりました）。この問題を正解できていたら3位以内に入れていたかと思うと、解法が思いついていただけに悔しい思いをしました。PGBattleの難しさでもあり面白さでもあるのですが、ルール上確実に正解を取りに行くということが非常に重要だったと再認識しました。また、テストケースが用意されているものだけでは（おそらく意図的に）不十分になっているので、自分でケースを考えて作成する力が特に求められていると思いました。
PG BATTLE には毎年参加させていただいて、力試しの場としてとても良いコンテストであると感じています。難易度の高い問題を比較的速く解法にたどり着けたことは良かったと思うので、今回見えた課題は今後の糧として精進していきたいです。
堅実に戦略的撤退したせんべい
せんべい担当の見習いスパルタ人2号です。普段は地点検索システムの開発をしています。
AtCoder のコンテストで出題された過去問をほぼ毎日1問以上解いており、レーティングは1900前後です。
業務では Kotlin/Rust を使っていますが、競技プログラミングでは C++ を使用しています（多倍長整数が必要な場合は Python を使う場合もあります）。業務ではより安全かつ宣言的に書きやすいRustなどをより好みますが、多少雑な実装でも素早く書きたいという状況が生まれやすい競技プログラミングにおいてはC++の懐の深さがフィットしていると感じています。
ここ数年せんべいを担当していますが一昨年はケアレスミス、昨年は実装力不足でいずれも4問中3問しか正解できませんでした。今年こそは悔いの残らないパフォーマンスを出せればと思っていました。
当日の様子
当日、1問目は累積和を使うことで計算量削減が可能なものの、計算量的に愚直なシミュレーションを行っても実行時間制約を十分満たせる制約サイズの問題でした。比較的バグらせやすい累積和実装を避け、愚直な実装でコーディング・見直し時間を最小化できたのは良い判断だったと思います。
2,3問目も比較的自分にとってやりやすい問題だったので、ここまで3問合計20分程度ですんなり解くことができました。
しかし、4問目が非常に難しかったです。制約の一部（スコアをk乗してから足す部分）を緩和すれば比較的シンプルな木構造グラフ上の動的計画法で解けることは分かったのですが、それをk乗する場合に拡張する立式で詰まりました。
30分ほど粘って考えましたが、時間内に解ける気配が全くしなかったのでその時点で提出しました。提出した3問はいずれも正解しており、約50分で70点というスコアになりました。
終わってみての感想
コンテスト終了後のSNS上での反応などを見ても4問目は「せんべいに鋼鉄が混じっている」と言われるほどの難問だったようでした。多少粘っても思いつかなかった時点で撤退、という判断は間違っていなかったと思います。結果解けていないのでもう少し早く提出することも可能でしたが、粘った結果解けた可能性も0ではないのである程度今の実力でやるべきことはできたと感じています。
とはいっても解けなかったものは悔しく、普段から難しめの問題をもう少し解いていれば手が届いたかもしれない難易度だったので精進に身を入れたいと思いました。
PGBATTLEと他のコンテスト
AtCoderなどの一般的なコンテストは強い（レートが高い）人がある程度安定して勝ち続ける傾向にあるのですが、PG BATTLEは
提出が1回限りなので、ちょっとしたミスによる大逆転が起こりやすい。社会人の部では赤コーダーがいなくても入賞するチャンスがある
解けない問題にどのタイミングで見切りをつけるか、が順位に影響するため「全部なるはやで解く」だけではない戦略性がある
という点でユニークで面白いコンテストだと感じています。AtCoderのような full-feedback形式 (提出後すぐに正解不正解が分かり、不正解なら再提出が可能なシステム) のコンテストしか出たことが無い方にもぜひお勧めしたいです。
見直しに救われたかつおぶし
かつおぶし担当のフジクジラ🐋です。普段はナビゲーション向けの測位技術の研究開発をしています。
AtCoderのコンテストにはほぼ毎週参加しており、レーティングは2100前後(黄色) です。
業務ではC++を使っていますが、競技プログラミングではRust を使用しています。元々は競技プログラミングでもC++を使っていたのですが、ある時期からRustの勉強のためにRustで取り組むようになりました。そうしたらいつの間にかRustが気に入ってきて、今では単にRustが好きだからRustでやっています。RustはC++同等の速度でありながらモダンな機能が入っているのが好きです（特にIteratorのメソッドが充実しているのが気に入っています）。
本番前の意気込み
私は昨年のPG BATTLE 2021でもかつおぶしを担当したのですが、そのときは4問中3問正解でした。今年はさらに+1問して4問正解することが目標でした。
基本的に4問目が一番難しいので、4問目に充てる時間を確保するために1〜3問目を素早く解きたいと考えていました。
当日までは、PG BATTLEに出そうな難易度のAtCoderの過去問を重点的に解いて備えました。
以下、当日の様子です。
1問目
1問目は、途中の項が一つ欠損した等差数列が与えられるので欠損した項を出力する問題でした。
すぐに思いついたのが、入力された数列の各隣接項の差とその半分（項数が3で真ん中の項が欠損している場合のため）を公差の候補として全て試す方針でした。しかし少し落ち着いて考えると、最初と最後の項の差から公差を計算して元の数列を復元したほうがシンプルになることに気付いて、途中まで書いていましたが方針転換して書き直しました。
結果的にバグりづらいシンプルな実装にできたと思います。
2問目
2問目は、点が開始位置から直線状に壁面で反射しながら動いたときに、一定時間T後に目的位置に到達できるような開始角度の個数を求める問題でした。
まず壁面での反射をそのまま扱うのは難しいので、代わりに目的位置（tx, ty）を壁面に関して繰り返し鏡像反転させた位置を考え、そのそれぞれの位置に到達できるか、という方向で考えました。対象となる位置は無数にあるのでその中からどう候補を絞り込むかが問題ですが、x座標を決めれば距離の関係からy座標も決まってくるので、対象のx座標を全通り試せばO(T)で計算可能であることに少し考えて気付き、その方針で実装しました。
y座標を求める際に平方根を取る必要があり、これを浮動小数点数にキャストしてsqrt()を使って実現していたのですが、入力が大きいときに精度が問題ないか少し気になりました。しかし、今回扱う数がT^2≦4×10^10程度なのに対して、倍精度浮動小数点数の仮数ビットが52ビットで、誤差なく扱える範疇なので問題ないと判断しました。
また、たとえばtx=0やtx=Wのケースがあると、壁面に関して鏡像反転したときに元と同じ位置になるので、重複カウントしないように注意が必要だと思ったのですが、今回の問題では制約でそのようなケースが除外されており、安心しました。空間的な問題は少し頭の中でイメージするのが苦手で混乱してしまいがちなので、このケースが除外されていなければもう少し時間がかかってしまっていたと思います。
3問目
3問目は、入力値からある規則に従って生成されるグリッドについて、これまた入力値で指定される複数のマス目の値を出力する問題でした。
手元の計算用紙に各マス目の値が入力値でどう表されるか書き出してみると、各マス目の値はいくつかの入力値のxorで書けることが分かりました。さらに、各入力値からの寄与が独立に計算可能なので、ある一つの入力値だけが1・それ以外の入力値が全て0のときの答えが計算できれば、それを全ての入力値について求めてxorを取れば答えが求まることも分かりました。
1列目の入力が全て0のとき、グリッドの各行は1行目の入力を繰り返し累積xorした値になっています。一般に、繰り返しの累積操作における寄与は二項係数で書けるので、あとは（同じ値を偶数回xorすると0になるので）二項係数の偶奇が分かればよく、これは簡単な式で書けることは覚えていたので「二項係数 偶奇」で検索して上位に出てきたサイトの結果を参照しました。1行目ではなく1列目からの寄与も対称性から同様に計算できます。
実際には、各入力値からの寄与を二項係数で表現するところで、二項係数の引数に自信が持てず、何度か導出と検算を繰り返して時間を使ってしまいました。繰り返しの累積操作の寄与を二項係数で表現する問題は以前AtCoderのコンテストでも詰まったことがあり、その際に復習はしていたのですが、十分に身に付けられていなかったようです。
ここまでの考察に基づいて実装したところ入出力例（テストケース）は通ったのですが、出力例の説明の中で、出力する必要のある一部のマス目の値だけでなく、グリッドの全てのマス目の値が書かれていることに気付きました。
そこで念を期すため、全てのX、Yの値に対して解を出力するように手元のプログラムを一時的に変更し、上図のグリッドと一致するか確認しました。
結果的にはこの行動が大正解で、X=1やY=1のときの出力値が異なっていることが分かりました。X=1やY=1のときは入力された値をそのまま出力するだけなので、問題ないと思っていたのですが、ケアレスミスで出力すべき値を誤っていたのです。
誤っていた箇所を修正し、グリッドの全ての値が一致することを確認して、（一時的に変更していた箇所を戻して）3問目は完了です。
4問目
ここまでの2問目や3問目で想定以上に時間を使ってしまい、当初の「1〜3問目を素早く解いて4問目にたっぷり時間を使いたい」という目論みが崩れてしまったので、かなりあせりながら4問目を開きました。
4問目は、一定のルールに基づいてグリッド上に駒を配置するときの、ありうる盤面全てのスコアの総和を求める問題でした。
グリッドに駒を配置する問題であることとN≦13という制約を見た瞬間に、これはbit DPの問題の可能性がありそう、と思いました（bit DP: 集合ごとに値を持つ動的計画法で、特に集合をビット列で表現して実装するテクニック）。
改めてルールを確認して解法を考えたところ、やはりbit DPで解けることが分かり、特に引っ掛かるところもなく実装することができました。
結果的に、3問目までは当初予定よりも時間を使ってしまいましたが4問目が比較的得意な問題だったので、なんとか時間内に4問全て解くことができました。
結果は100点で提出時間は73分でした。
終わってみての感想
普段AtCoderで参加しているコンテストとは異なりチーム戦なこともあり、3問目で手間取ったときは非常にあせって心臓がばくばくいっていました。このあたりはチーム戦ならではの緊張感だと思います。
3問目のバグにコンテスト中に気付けたのは良かったです。今回は入出力例の説明の中で様々なXやYに対する解が提示されていたためにそこの挙動を確認しようと思うことができましたが、そうでなければバグに気付けなかったかもしれないと思います。PG BATTLEのようなコンテスト終了後まで正解/不正解が分からないコンテストでは見直しの重要度が大きいので、来年以降は特にコーナーケースでの挙動確認を徹底していきたいと思いました（開発物のリリース前の検証は業務でも超大事です）。
来年のPG BATTLEにも参加できた場合は、引き続き4問解くこと&提出までの時間短縮を目標にしたいです。
競技プログラミングと業務
PG BATTLEに限らない競技プログラミング一般の話にはなりますが、ナビタイムジャパンのnoteで競技プログラミングの話をする機会も滅多にないので、競技プログラミングと業務の関わりについて、少し書いてみたいと思います。
業務にどう生かされているか
前提として、ナビタイムジャパンでは、基本的に全てのサービスを内製しており、結果的にスマホアプリ開発から経路探索アルゴリズム開発まで多様なプロジェクトが社内に存在しています。そのため、「競技プログラミングの経験が普段の業務においてどう生かされているか」も、個々の開発者によって全く異なります。以下の内容は、あくまで私たち3人の担当してきた業務の範囲におけるものとしてご理解いただければと思います。
まず、競技プログラミングで出てくるようなアルゴリズムをそのまま業務で使うことがあるかというと、実は一部のアルゴリズムについてはその機会があります（例として、深さ優先探索、ダイクストラ法、素集合データ構造、動的計画法など）。もちろん使わずに済ませることができる場合もありますが、既存のアルゴリズムを使うことでより簡単に書けたり、より効率的な処理が実現できたりします。
一方で、高難度の問題で要求されるようなより高度なアルゴリズムについては、業務で使ったことはありません。そういう意味では、一定以上の高レベルな知識は業務ではそのまま役に立たないと言えるかもしれません。
しかし、競技プログラミングで培われる力はアルゴリズムの知識だけではありません。複雑で既存のアルゴリズムがそのまま適用できないような問題について、いかにそれを解決するか考え抜く思考力・忍耐力は競技プログラミングで鍛えられると思います。少し込み入った程度のものであれば、さっと書き切ることができるということもあります。そういう観点では、アルゴリズムコンテストよりも、特に長期のヒューリスティックコンテストのほうが実際の業務で考えることに近いかもしれません。
参考までに、ナビタイムジャパンのプレスリリースで、アルゴリズムの要素が強いものとしてはたとえば以下があります:
他に培われたこととして、競技プログラミングの経験により計算量の観点が身に付いたことが挙げられます。たとえば、深く考えずに計算量がO(N)かかってしまう標準ライブラリのfind()（線形探索）関数を何度も呼んでボトルネックになってしまった、といった事態に（自分が書くときもレビューするときも）未然に気付きやすくなります。また、「10^8回程度の計算を行うと秒単位で時間がかかりうる」という具体的な感覚もパフォーマンスを考える上で役立つことが多いですし、逆に「10^3回程度の計算ならそこまで時間がかからない（ので多少非効率でも読みやすいシンプルなロジックで十分）」といった力の抜きどころも分かります。
業務との違い
競技プログラミングと業務との違いについても触れたいと思います。業務で出会う問題は、競技プログラミングの問題とは異なり、制約や前提条件がはっきりしていなかったり、入力にノイズがあったり、実世界の問題ならではの難しさがあります。時にはそもそも何を解決すべきなのか、なにを入力として受け取るべきなのか、問題設定自体について一から考え直すことも要求されます。競技プログラミングでは直接このような問題を取り扱うことはありませんが、こういった問題に立ち向かうのに必要な思考力の土台は、競技プログラミングで培うことができると思います。
また業務では、いわゆる定数倍高速化（理論上の計算量のオーダーは変わらずとも、計算量の問題サイズに対する係数を改善すること）も重要になることがあります。定数倍高速化は、競技プログラミングではあまり重視されないことが多いですが、たとえ計算量のオーダーは変わらずとも、ある処理を2倍高速化することができれば、ユーザーとしても嬉しいですし、クラウドのコストも半分になります。ボトルネックを一つずつ定数倍高速化していくのは、泥臭くもありますが、重要でやりがいのある仕事です。
まとめ
企業の部で6位という順位をおさめられたのは嬉しいですが、目標であった3位以内入賞はできませんでした。もっと精進して、来年こそは3位入賞を達成したいと思います。
また、もしこの記事を読んで競技プログラミングやPG BATTLEに興味が出てきた方がいれば、ぜひコンテストに参加してみてください！ 業務との関わりも書きましたが、実際のところそれを抜きにしても競技プログラミングはとても面白いのでオススメです。