競プロ部をつくって PG Battle 2021 に参加しました

モノグサ株式会社のソフトウェアエンジニア、Tobisatis (@tobisatis)です。今回は、当社の部活のひとつである競技プログラミング部（通称、競プロ部）より、活動報告をお届けします。

競プロ部は、2021年8月に設立された部活です。競技プログラミングが趣味の社員が順調に増えてきた頃を見計らって、4人以上のメンバーが集まりそうだと確信を得てすぐに設立宣言をしました（当社では4人以上の部員を集めることで部活を設立できます）。競プロ部のSlackチャンネルには、現在12人が参加しています。

モノグサ競技プログラミング部として初めての大会参加として、2021年10月23日開催の「PG BATTLE 2021」に出場しました。PG BATTLEは、同じ会社内や学校内の3人を1チームとして出場する競技プログラミングの団体戦です。学生向けと比べて社会人向けの団体戦は開催される数が少ないため、会社で参加できる貴重な機会となりました。

チーム結成

競プロ部設立直後の集会で話し合いを行い、1チームが結成されました。出場する3人のメンバーは、AtCoder（日本最大の競技プログラミングのサービス）でのレベルがそれぞれ黄色、黄色、青色です。当日に解く問題は、普段のコンテストの成績などを考慮して決められました。チーム名はメンバーで話し合い、「モノグサで行こう」に決まりました。

問題と考察

それぞれのメンバーが大会中に行った考察を一部紹介します。解法などを含みますので、問題を自力で解きたい方は解いてからご覧ください。問題は公式サイトから確認できます。 products.sint.co.jp

・ましゅまろ2問目

次の考察で正解となります。

・ましゅまろ3問目

範囲内のすべてのマスを使って目的地に行く場合の数から、封鎖されたマスを通って目的地にいく場合の数を引いて解くことができました。封鎖されたマスが範囲外であるパターンにも気づいて正解できました。

・ましゅまろ4問目

数列の数え上げ問題で、尺取り法を使って解くことができました。与えられたテストケースが少ないこともあり場合分けが正しいか不安でしたが、テストケースを自作することで正解できました。

・せんべい2問目

最大値最小値を求める問題で、二分探索によって解くことができました。バグを解消するのに時間がかかりましたが、丁寧に作成したサンプルケースの成果もあり正解できました。

・せんべい4問目

UnionFindを使った貪欲法などを考えていましたが、十分に早い方法を時間内に思いつけませんでした。

・かつおぶし1問目

ある整数の階乗の桁数を求める問題で、対数などを用いて解くことができました。数学の関数を使いやすいPythonに切り替えて解いたところ、正解できました。

・かつおぶし3問目

imos法のような考え方の実装に挑みましたが、時間内に解ききれませんでした。

結果と振り返り

12問中8問を正解し、全体で19位でした。出場したメンバーはチーム結成以降、AtCoder（日本最大の競技プログラミングのサービス）でほぼ毎週開催されるコンテストに出場して、結果や考察の共有を社内のSlackで行っていました。本番はAtCoderのコンテストとの形式の違いなどで慣れない点もあったようですが、日頃の練習の成果もあり、大変良い結果を残してくれたと私は感じています。