こんにちは。エンジニアの田屋です。フォルシアの競技プログラミング部(以下、競プロ部)では、「ゆるふわ競技プログラミングオンサイト(以下、ゆるふわオンサイト)」という、競プロ部員が作問・運営を行うオンサイトのコンテストをこれまでに6回開催しています。過去のイベントや競プロ部の活動の様子はこちらの記事もあわせてご覧ください。
競プロ部では9月末に第7回ゆるふわオンサイトを開催しました!
開催前の準備
今回のゆるふわオンサイトは、今年入社した新卒社員が主導となってイベントの準備をしました。コンテストの運営責任者を私田屋が、問題原案から問題セットを組み、作問作業全体の進行管理などを行うコーディネーターを同じく新卒エンジニアの城武さんが担当し、競プロ部員を中心に企画の運営をしました。
競プロ部員から問題の原案を募り、原案を解いたりその原案から強化したりしてチームで作問作業を行いました。ゆるふわオンサイトは初心者から強者まで幅広い層にわたって参加されるので、どんな方でもなるべくコンテスト時間いっぱいまで問題に取り組めるようコンテストセットの作成を目指します。これまでは問題を解く側でしかなかった私も初めて作問してみました。
コンテストセットを組む過程で、「最後の2問を同じ点数にしたら面白いんじゃないか?」という話があがりました。一番難しい、いわゆるボス問題とされる最後の2問は解く方の好みにも左右されやすいことから、同じ点数にした方が参加者の戦略性が上がるのではないか、ということで同じ点数にする試みを採用しました。
結果として2時間半で9問のコンテストセットが組まれました。コンテストページは こちら です。
コンテスト当日の様子
当日は、オープニングと会社紹介の後、コンテストがスタートです。まずは無事コンテストがオープンしているかを見守ります。開始1分後、順調に問題が解かれ始めている様子が確認できて安堵です。
コンテスト終盤ではボス問題枠であるH問題とI問題に、ほぼ同じ時間に正解者が現れ、運営側は大いに盛り上がっていました。最終的にすべての問題を1人以上に正解していただき、運営側も大満足でした。
強者たちも多く参加する中で、ボス問題の片方を見事正解した potato167さん が優勝しました!
ゆるふわ競技プログラミングオンサイト at FORCIA #7 コンテストページ順位表
コンテスト終了後は、問題の作成者による解説を行った後に、ピザやお菓子などを食べながら懇親会を行い、問題に関する感想を話し合ったりしながら、オンサイト参加者の皆様と社員で交流しました。中にはボードゲームを持って来られた方もおり、懇親会は時間いっぱいまで大賑わいでした。参加者の方々には最後にアンケートに回答していただき、イベントの感想を伺いました。
コンテストで出題された問題の例
ここでは実際にコンテストで出題された問題をいくつかピックアップして紹介します。解いてみたい方は、 https://mofecoder.com/contests/yurufuwa_onsite_07 からコンテストページに飛んでいただいてぜひチャレンジしてみてください!
D問題:Taking Sandwitches
- https://mofecoder.com/contests/yurufuwa_onsite_07/tasks/yurufuwa_onsite_07_d
巨大なサンドイッチの中から小さいサンドイッチをつまんでいくような問題です。原案当初は「各数字がそれぞれちょうど2回ずつ現れる」という制約でしたが、別の競プロ部メンバーの「同じ数字は何度でも出てきた方が面白い」という意見によりその制約が取り除かれ、問題がアップデートされました。それもあってか、参加者アンケートでも最も評価の高かった問題となりました。
この問題は配列を前から見て、最小値を更新していく動的計画法によって解くことができます。また、最短経路問題と解釈して解くことも可能なので、ぜひ色んな解法で解いてみて欲しいです。
性質に気づけるとシンプルですが、ハマると大変という印象です。私は最短経路問題として解こうとして辺の張り方に苦戦してしまいました。
G問題:Dot Product Query
- https://mofecoder.com/contests/yurufuwa_onsite_07/tasks/yurufuwa_onsite_07_g
私が競技プログラミングをはじめてから初めて作成した問題です。もともと作問が苦手で、なかなかアイデアが思いつかない中で、「2つの数列を用いてシンプルな設定で何か問題が作れないか」と考え生み出された問題でした。コンテストに採用されて嬉しいです。
問題の概要は「数列AとBの要素ごとの積の総和がCとなるよう、Bの値を変えてください。ただし変えるBの要素の個数は最小化してください。」というものです。以下の問題の例も参考にしてみてください。
その後、高速化の観点で考慮しなければいけない点がいくつかありますが、コンテスト時間内には6名の方が見事正解していました!
この問題は「Aの要素をランダムにいくつか選ぶのを時間いっぱい試行する」という乱択解法が強いのですが、その解法を弾けるような、強いテストケースの作成方法を競プロ部員に助言をいただきながら、テストケースの作成をしました。
その他すべての問題の解説は https://speakerdeck.com/forcia_dev_pr/di-7hui-yuruhuwaonsaitojie-shuo に掲載されておりますので、こちらもあわせてご覧ください。
おわりに
今回は新卒社員が主導となりイベントの企画を行いました。コンテストを運営していくのは大変でしたが、競技プログラミングに関して競プロ部員たちと議論しながら、チームでコンテストを作り上げていくのは非常に楽しかったです。
競プロ部では今後も継続的にゆるふわオンサイト開催に向けて取り組んでいきますので、興味の湧いた方はぜひ参加してみてください!
フォルシアでは、競プロに取り組む皆様を応援するため、CodeQUEENや競プロキャンプなどのイベントに協賛してきました。今年は、国際的な大学生向けコンテストであるICPCでもスポンサーとして協賛させていただきます。ICPC 2024 横浜大会 では競プロ部員も弊社ブースにおりますので、立ち寄っていただけると嬉しいです!
また、競プロ以外ではPostgreSQL Conference Japan 2024 や、ISUCON14 でもスポンサーをしておりますのでぜひご参加ください!
最後に、今回はF問題の問題文に不備があり、参加者の皆様にご迷惑をおかけしてしまい申し訳ございません。これからも多くの方にゆるふわオンサイトを楽しんでいただけるよう、競プロ部では改善を続けていきます。競プロ部に興味をもっていただけた方はぜひ 採用ページ にとんでいただいて、今後のゆるふわオンサイトを一緒に作っていきましょう!
田屋 大輝
フォルシア1年目エンジニア
PostgreSQL Conference Japan 2024 には運営スタッフとして、ISUCON14 には選手として参加予定。
フォルシアではフォルシアに興味をお持ちいただけた方に、社員との面談のご案内をしています。
採用応募の方、まずはカジュアルにお話をしてみたいという方は、お気軽に下記よりご連絡ください。
※ 弊社社員に対する営業行為などはお断りしております。ご希望に沿えない場合がございますので予めご了承ください。