新卒4年目、プロダクト部の松本です。

フォルシアで働き始めてから毎年春に社内で競技プログラミングのコンテスト、通称「ニクの日プロコン」を開催しています。社内コンテストでありながら、過去問を利用するのではなく、社員が問題を自作するのが特徴で、毎年4問から6問の問題を準備しています。普段は競技プログラミングをやっていないメンバーも参加するため、簡単な問題から、アルゴリズム改善が必要な骨のある問題まで幅をもたせて出題をしています。

今年もニクの日プロコンを開催しました。今回はフォルシア競プロ部から、淺野・遠藤・松本の３名で合計5問を作成しました。ちなみにコンテスト時間は60分です。

コンテストは自席でもくもくと問題を解きます。業務で書く量の多いJavaScriptやPythonで実装する人が多いようでしたが、ガチで1位を狙う人もいれば、勉強中のRustでコーディングするインターン生もいて、取り組み方は十人十色でした。

昨年の様子はこちらの記事『毎月29日は「ニクの日」フォルシアのエンジニアは肉を食べ、技術を語らう』を御覧ください。

問題紹介

実際にコンテストで出題した問題から2問紹介します。

遠藤さんが作った問題

作問は今回が初めてという遠藤さんの作った問題がこちら。

問題文

ある会社F社には、二種類の炭酸飲料T, Lが冷蔵庫に用意されており、社員はいつでもそれらを飲むことができます。F社の社員が炭酸飲料を飲む際には、３つのルールがあります。

1. みんなが一番冷えた飲料が飲めるように、決まった順番に沿って取ること。
2. 一本冷蔵庫から飲料を取ったら、倉庫から新たに一本を奥（順番の最後尾）に置くこと。
3. 新たに一本飲料を置く際には、取った飲料「ではない種類」の飲料を一本置くこと。（「同じ種類」ではないことに注意！）

いま、冷蔵庫にはM本の炭酸飲料が入っており、それらは最初に取られるものから順に a_1, a_1, a_2, ... , a_M ただし、a_i = "T" or "L"（1≦i≦M） の順番に入っているとします。
冷蔵庫が上記の順番になってから、AさんがN人目として炭酸飲料を取りに来ました。
Aさんが手に入れる炭酸飲料はTとLのどちらでしょうか？

---

フォルシアの福利厚生であるフリードリンクから問題を作るパターンですね！
難しいアルゴリズムを使わなくても解ける競プロ未経験者にも優しいところを見せながら、愚直に実装すると複雑になるという問題になっています。周期 2M がポイントですね。

もくもくと問題に向き合う社員。

淺野さんが作った問題

もう一問、作問2年目の淺野さんの問題をどうぞ！

問題文

2つの自然数N,Mが与えられます。 次のような漸化式を満たす数列{a_n} について、M項目の数a_Mを10^9 + 7で割った余りを出力してください。

• a_i = 0 (i <= 0)
• a_1 = 1
• a_n = a_(n-1) + a_(n-2) + ... + a_(n-N)

解説

シンプルな解法として、iについてループを回し、a[i]を添え字の小さいものから順に求めていく方法があります。a[i]の値を配列に保持しておくことで、O(NM)でa[M]を求めることができます。

今回はO(NM)でも十分間に合う制約で出題しましたが、もう少し高速化して線形オーダーで解くこともできます。

下記の2式

a[i+1] = a[i] + a[i-1] + ... + a[i-N+1]
a[i]   =        a[i-1] + a[i-2] + ... + a[i-N]

から、

a[i+1] - a[i] = a[i] - a[i-N]
a[i+1] = 2a[i] - a[i-N]

と変形できます。

a[i+1]をO(1)で求めることができたため、O(M)でa[M]を求めることができました。累積和を用いても同様にO(M)で求められます。

---

初心者も点数を取れるように配慮しながらも、アルゴリズムを考える楽しみの伝わる問題になっていますね。解法の検討がつかない問題を考えるのも楽しいですが、時間をかければ計算は出来るのだけどアルゴリズムを改善すれば桁違いに速くなるという経験は競技プログラミングの醍醐味だと思います。

初作問の感想は？

一問目の遠藤さんは今回が初めての作問ということで、感想を聞いてみました。

社会人になってから競プロを始めたため、今年で２年目なのですが、競技プログラミングの問題を作るというのは初めてでした。
普段競技プログラミングの問題を解いているときと比べて、問題に対して深い考察が必要になると感じました。
また、回答に対して様々なコーナーケースを含め厳密に検討するということができてとても勉強になりました。
競技プログラミングに限らず、エンジニアとしてとても良い経験になったので今後も作問含めて競技プログラミングに取り組んでいきたいです。

表彰式・解説

会議室に移動して、お弁当を食べながら、表彰や解説を行いました。

ニクの日の定番弁当。（お気づきですか？昨年と同じ弁当です。）

優勝はなんと今月入社したばかりで、今はジョブ・ローテーション中の髙橋さん。学生時代に研究でデータ解析をしたり、独学でPythonを勉強していたということで、地頭の良さを見せつけていただきました。今後の活躍が楽しみです！

賞品

今回はエンジニアの好奇心を駆り立てるガジェットということでヘッドマウントディスプレイのOculus Goを賞品に用意しました。

GWに使い倒して、いいアプリ作りに活かしてもらえればと思います。

競プロ部のメンバー募集してます

フォルシア競プロ部は、毎週蟻本の輪読やもくもく会をしたり、社内でプログラミングコンテストを開いたりと活動をしています。
もちろん日中は高速な検索プラットフォームの開発やお客様サイトの開発をしています。
競技プログラミングで得られる知識の中でも、特にデータ構造の知識は高速検索に欠かせません。

競技プログラマーの方向けに応募しやすいAtCoderJobsからのご応募もお待ちしています。