本稿はJCB Advent Calendar 2022の１２月１６日の記事です。
JCBデジタルソリューション開発部 アプリチームの鬼沢です。本日はPG BATTLE 2022というイベントに参加したため、その紹介をします。
PG BATTLEとは
PG BATTLEとは3人1組で参加する企業・学校対抗のプログラミングコンテストです。出題された問題を解く競技プログラミングの形式です。難易度が「ましゅまろ」「せんべい」「かつおぶし」の3つ（固いものほど難易度が高い）に別れており、それぞれ担当者を決めて問題を解き、3人の合計点および回答時間で順位が決まります。開催はオンラインで、2022年は10月22日（土）に実施されました。
参加メンバー
私とは別のアプリチームに所属している古市さん、村井さんと共に参加しました。
| メンバー | 担当 |
|---|---|
| 古市さん | かつおぶし |
| 鬼沢 | せんべい |
| 村井さん | ましゅまろ |
参加準備
競技プログラミングではC++がメジャーなため、普段はGo言語にて開発していますがC++で参加することにしました。事前にエディタやコードのテンプレートを用意したり、典型90問を解いたりPG BATTLEの過去問を解いて準備をしました。過去問では3問解けたため本番でも3問、あわよくば4問解きたいなと思っておりました！
※ 出題される問題は全部で4問。全問正解だと100点です。後半の問題になるほど難易度が高く、配点も多くなっています。
当日の感想
当日の問題はこちらから閲覧できます。正しい答えを出すだけではなく指定された実行時間、メモリ量に収まるプログラムを作成する必要があります。私はせんべい担当でしたので、以下はせんべいの問題を解いた感想です。基本的に問題を解いた人でないと伝わらない部分が多いと思いますが、雰囲気だけでも感じて頂ければと思います！
１問目
Q回与えられた区間のせんべいを裏返し、最後に裏返っているせんべいの枚数を答える問題でした。いもす法を使えば効率的に計算できそうだ！と思いましたが、制約で与えられた数が小さく時間制限に引っかからないため愚直な方法の方がバグらせずに済むなと思い、1枚1枚せんべいを裏返す実装にしました。担当した難易度であるせんべいに関連する問題で面白いですね！
２問目
こちらもせんべいに関連する問題でした！3N個の食品の固さが与えられ、何番目がせんべいかを求める問題でした。元の番号を覚えておきながらソートしてせんべいの番号を求め、さらにそれをソートすることでせんべいの番号を昇順に出力できました。といあえず2問目までスラスラ解け、少し安心です。
３問目
与えられた整数の配列から1、2、3、4のように1から1づつ大きくなっている部分を任意の回数削除し、最後に残った数字の合計を求めたとき、最小となる合計値は何か？という問題でした。こちらは配列の後ろから数字を見ていき、1がきたらなるべく多くの数を消すという方針でいけば良いことに気づけ、無事実装できました。ここまでで90分うち20〜30分しか経過しておらず、今年は問題が簡単だな。4問いけるかも！？と思っておりました。ところが計算量の想定が間違っており、TLE（実行時間の制限超過）で不正解となりました。例年の問題よりとても早く解けていたということから本当に回答が合っているのかもう少し考えるべきでした。詳細は結果の部分に記載します。
４問目
グラフに関する問題ですが、とても難しそうでした。まず答えの算出方法が思い浮かばない。思い浮かんだとしても計算量の工夫も必要そうでした。自分の実力より数段上な問題だと判断し、回答時間も順位へ影響するため解かずに撤退しました。実際かなり難しい問題で時間をかけても解けないレベルだったため、点数より回答時間を優先して正解でした。
結果と今後について
古市さん20点、鬼沢40点、村井さん40点の合計100点獲得し、189チーム中75位という結果になりました。初参加にしては上位50％に入れ善戦したと思っています。
個人的には3問目が不正解で残念でした。原因はvector型の要素削除をO(1)のつもりで書いていたのですが、実際はO(N)で実行制限時間に引っかかったことです。1度しか提出できないのがPG BATTLEの難しいところですね。
他メンバーも悔しい思いをしたようで、来年も機会があれば再挑戦しようと思います！
- PG BATTLE 2022の振り返り結果
最後になりますが、JCBでは我々と一緒に働きたいという人材を募集しています。 詳しい募集要項等については採用ページを ご覧下さい。
