「ゆるふわ競技プログラミングオンサイト at FORCIA #2」を開催しました

旅行プラットフォーム事業部の大沢です。

フォルシアにはサークル活動として競技プログラミング部（以下、競プロ部）があり、毎週過去問を解いたり輪読会をしてトレーニングに励んでいます。

社内イベントとしてコンテストを開催することもあります。
フォルシア競プロ部がニクの日プロコンを開催！

今回9/14(土) に競プロ部の有志で「ゆるふわ競技プログラミングオンサイト at FORCIA #2 ゴリラの挑戦状」というイベントを開催しました。

ゆるふわ競技プログラミングオンサイトとは？

競プロの大会では、予選をオンラインで行い、決勝に進むとオンサイト会場に招待されて、一堂に会して腕を競うことが少なくありません。

しかし決勝に進むというのは強者の特権であり、なかなか一般の競技プログラマには機会がないものです。

そこで、なかなかオンサイトに呼ばれる機会のない初級～中級の競技プログラマでもオンサイトの雰囲気や参加者同士の交流を楽しめるようにと、誰でも「ゆるふわ」っと参加できる競プロオンサイトのイベントを企画しました。

ゴリラの挑戦状とは？

「ゴリラの挑戦状」というサブタイトルは、私自身が普段ゴリラのアイコンで競プロをやっているところから(僭越ながら & 光栄にも) 付けました。

ゆるふわ競プロオンサイトは今回2回目の開催で、実は今年2月に行われた第1回のとき、私は参加者の立場でした。そこでフォルシアを知り、素敵な取り組みをしている会社だなと思い、入社に至った経緯があります。

ですので、私としてはある種の恩返しのつもりで、絶対に成功させたいイベントだと思っていました。

競プロの作問を行ったのは初めてでしたが、張り切って務めさせていただきました。

イベントレポート

コンテストの様子

イベント当日は30名の参加者が会場にお越しくださいました。オンラインでの参加を入れると、65名もの方がコンテストにご参加いただきました。

多数のご参加ありがとうございました。

コンテスト時間は2時間で、計12問の問題を出題しました。

プログラミング入門者が解ける問題から、競プロ上級者が頭を悩ませる(かもしれない)問題まで幅広い難易度を揃えました。

難易度によって100～600点の配点があり、制限時間内に正しい出力を返すプログラムを提出すると得点になります。

同点の場合は最後に得点が加算された時刻の早い方が順位が上になります。

問題数が多かったこともあり、オンサイト参加者は2時間最後まですごい集中力でPCに向かわれていました。

解説・表彰

少し休憩をはさんで、解説と表彰を行いました。

優勝は、なんと時間内(1時間48分49秒) で全問正解した、_primenumber氏(写真右) でした！

全問解けたのはオンサイト会場では1名だけでしたので、実力を見せつけての堂々の優勝でした！

また、事前に登録していただいたAtCoderのアカウントを使って、各レートの色(ランク)別にそれぞれ1位の方々も表彰しました。イベント名にちなんだ副賞として、バナナが渡されました。

親睦会

表彰後、ピザとドリンクを囲んで懇親会を行いました。土曜の夕方ですが、アルコールも少し！

皆さんコンテストの感想や、最近の競プロ界のお話、仕事や学業の話、マスコットの話、、、で盛り上がっていました！

競プロはお仕事の役に立つか？という(そこそこ定番の)話題もありました。

私の考えは、〇〇法が役に立った！みたいな分かりやすい体験はすごくレアですが、知らず知らずに役に立っているケースが多いんじゃないかと思っています(簡潔にコードを書く、計算量の感覚、コーナーケースの考慮、、など...)。

ホワイトボードでのアンケートがあり、こちらも盛り上がっていました。

使用言語、Lua... めずらしい...

Luaの1名とRustの1名を除くと、C++かPythonで二分化していたのが興味深いです。

競プロ歴、1.5～2年に集中していました。ゆるふわなので、始めて半年未満の方でも大歓迎です。

出題された問題の例

最後に、当日9問目に出題された問題を紹介します。

想定よりも多くの参加者を悩ませた、作者のお気に入りの問題です。

問題(概要)

「pino assort」

• N人の社員から、支払うコストが最小になるK人を選び出す問題
• コストはアイスの箱数で評価され、アイス1箱にはバニラ味が10個と、アーモンド味が7個、チョコ味が7個入っている
• i番目の社員を選ぶには、バニラ味がv_i個、アーモンド味がa_i個、チョコ味がc_i個必要
• コストが最小になるようにK人選ぶとき必要な最小の箱数を求める

制約

• 1 <= K <= N <= 100000
• 1 <= v_i, a_i, c_i <= 100
• v_i, a_i, c_iのうち少なくとも2つが1

解説

考慮する制約が多くて、一見どこから手を付けて良いかわからないかもしれません。

求めたいのは必要な最小の「箱数」なので、箱数に注目するのがよさそうです。

部分問題として 「x箱のアイスはK人を採用するのに十分か？」 が高速に求まれば、箱数を決め打った 二分法 が使えます。

実際この部分問題は、単純な貪欲法によって解くことができます。

以下その部分問題について解説します。

まずx箱と箱数を決めておけば、バニラ味は10x個、アーモンド味とチョコ味はそれぞれ7x個と配れる個数が求まります。

さらに制約に注目すると、

• どの人も、すべての味を1個ずつ欲していること
• K人を選んだ時に少なくとも各味K個のアイスが必要であること
• どの人にも各味1個ずつ配ったことにすると、あとは高々1種類の味のアイスしか欲していないこと

がわかります。

先に各味1個ずつを配る、というのがポイントで、これをすると

「バニラ味だけ欲する人」「アーモンド味だけ欲する人」「チョコ味だけ欲する人」「どれもいらない人」の4つに分類できます。

これで各味について独立に考えることができて、味ごとに必要個数が少ない人順に配っていけばそれが最適な割り当てになります。

最終的な解法としては、

• 入力を受け取ったら、事前準備としてそれぞれの人がどの分類に属するかを分類する
• 分類ごとに必要個数で昇順ソートする
• 部分問題を解く関数を作る (入力：箱数、出力：true|false)
  • 箱数から、それぞれの味のアイスが全部で何個あるか求める
  • K個に達しない味がある場合はfalseを返却する
  • 「どれもいらない人」がK人以上ならtrueを返却する
  • 各味について、必要個数の少ない人から割り当てていき、(「どれもいらない人」も含め) 割り当てがK人以上になればtrue、そうでなければfalseを返却する
• 部分問題の結果がfalseからtrueとなる境目を二分法で求める

のように実装すると求めることができます(上記は解法の一例です)。

開催してみての感想など

今回多くの人が楽しめるように、2時間のコンテスト時間に対して12問と多くの問題を幅広い難易度で出題しました。なんと当日出題した12問のうち11問は私の作問でした。すごく張り切ってしまいました。

5月末ぐらいから少しずつ準備を始めていたのですが、7月にオンラインでイベント参加者の募集をしたときにすごい勢いで枠が埋まってしまって、とてもテンションが上がったのが記憶に新しいです。
参加者一覧には私よりはるかに上位の猛者たちの名前も多くあり、このままでは簡単に全部解かれて暇になってしまう！この人たちにも最後まで楽しんでもらいたい！との気持ちが強くなりました。

すでにゆるふわなコンテストを開くには十分な量の問題案が揃っていたのですが、8～9月は追加で出題しようとかなり頭をひねらせました。
その甲斐もあってか、懇親会などで、最後まで頭を使った！楽しかった！また参加したい！などのポジティブな感想を色々な層の方から頂けて、本当にがんばって良かったと感じました。

特にトラブルなく最後まで解いてもらえたのもうれしかったです。また、自分の作った問題に頭を悩ませてもらえるというのは、こんなに幸せなことなのかと感じました。

オンサイトに初めて参加された方も多くいらっしゃって、参加者同士が楽しく交流している様子を見ると、主催者としては大成功だったと感じます。

開催にあたり、問題のtesterをボランティアで引き受けてくださったきゅうりさん・りあんさんのお二方にはこの場を借りて御礼申し上げます。testerとのディスカッションを通して問題の質を上げることが出来ました。

ご参加くださった皆様、本当にありがとうございました！

さいごに

フォルシアのオフィスにはいつ飲んでも良いフリードリンクと、いつ食べても良いフリーピノが用意されています。今回の「pino assort」の問題もピノアイスを食べているときに思いつきました。気分転換に嬉しいですね！

フォルシアには他にも魅力的な福利厚生が充実しています！ご興味をもたれた方は、採用ページもぜひご覧ください！