こんにちは。エンジニアの城武です。
フォルシアの競技プログラミング部（以下、競プロ部）では、「ゆるふわ競技プログラミングオンサイト（以下、ゆるふわオンサイト）」を過去 7 回開催しています。
前回のゆるふわオンサイト開催レポートや、普段の競プロ部の活動の様子は以下の記事も是非、合わせてご覧ください。
競プロ部では 5/31 に第 8 回ゆるふわオンサイトを開催しました。
開催に向けた準備
今回のゆるふわオンサイトでは、当日のオンサイト会場設営に向けた準備の統括・管理はエンジニアの大沢さんが担当、コンテストの作問作業の進行管理は私が行い、競プロ部を中心に企画の運営を行いました。
少し話は逸れますが、最近の競プロ部の活動では今年新卒入社した新入社員の方も普段の活動に参加して競技プログラミングに興味を持っていただいており、その中で新入社員の石坂さん・髙橋さんが今回のゆるふわオンサイトの運営のお手伝いをしてくださりました！ありがとうございます！
次に問題準備についてですが、コンテストの問題選定においては、以下の 2 点を意識していました。
- ゆるふわオンサイトでは初心者～熟練者まで幅広い層が参加するので、問題の難易度もなるべく幅広く用意する。また、後半の難しい問題にも部分点を設定して、時間いっぱい楽しんでいただけるようにする。
- 考察要素が強く、考えていて楽しい問題を用意する。
結果、コンテスト終了後のアンケートでも「考えていて楽しかった」「頭を使う問題が多かった」「部分点のおかげで難しい問題にもチャレンジしようと思えた」とポジティブな感想をいただけました。
また、コンテストの問題準備の進行管理では、前回問題文に不備があったことの反省を踏まえて、準備をなるべく早めに行うことを意識していました。その結果、問題に関する準備はこれまでで一番余裕があり、問題文の細部の表現やテストケースの強さにこだわったり、当日の運営準備に気を配る事ができました。
今回のゆるふわオンサイトの問題は こちら から閲覧することが出来ます。
ゆるふわオンサイト当日の様子
当日は応募いただいた 30 名の方をフォルシアのオフィスにお招きして、コンテストを開催しました。また、オンラインからも 25 名の方にコンテストに参加いただきました。
コンテスト中、運営陣は参加者が問題を解く会議室とは別の会議室で、順位表を見守りながらワイワイと盛り上がっていました。
今回も熟練者が多く参加する中、オンサイトで唯一全問正解し、前回に引き続き potato167 さんが連覇を達成しました。おめでとうございます！
ゆるふわ競技プログラミングオンサイト at FORCIA #8 コンテストページ順位表
コンテスト終了後は、作問者による解説を行った後、表彰を行いました。
その後は、ゆるふわオンサイト恒例の懇親会が開かれ、ピザやお寿司などを囲みながら楽しいひとときを過ごしました。会場では、参加者同士はもちろん、社員と参加者のあいだでも活発に交流が行われました。
コンテストで出題した問題
今回、第 8 回ゆるふわオンサイトで私が出題した問題について、出題の経緯や感想を述べたいと思います。
今回私が出題した問題は以下の 2 問です。
D問題：Range Mod Query
正整数列 A に対して区間 l, r がクエリとして Q 個与えられるので、A の l 番目の要素に対して l+1, l+2, ... r 番目の要素で割ったあまりを順に計算し、その結果を答えるという問題です。
考察要素がありつつも、データ構造も活用する必要があるようなクエリ問題を作りたいと思いながら作成しました。シンプルな問題なので過去に全く同じ問題がどこかで出題されているのではないかと懸念していましたが、時間をかけて調べても見つけられなかったため原案として提案するに至りました。
この問題はあまりの性質に着目し、セグメント木というデータ構造を上手く活用することで高速にクエリに答えることが出来ます。
想定解法の計算量は O(Q log(N) log(max(A_i))) ですが、より良い計算量の解法も存在するかもしれません。
E問題：Insert or Swap
1つの箱と N 個のボールがあり、各ボールについて「そのまま箱に入れる」か「既存のボールを 1 つ捨てて入れ替える」のいずれかを順番に選んで、最終的に箱にボールを K 個残すときの総コストの最小値を求める問題です。
考察が必要ではあるが、実装はシンプルであるような ad-hoc な問題を出題したいという思いから作成しました。
この問題は私が日々の生活で感じたことから作りました。具体的には通勤の際、満員電車に乗っている時に「満員電車は人が多く乗っていればいるほど乗り降りが大変だな」と感じ、そこから満員電車を箱、人をボールに置き換えて、「箱とボールがありボールを入れ替える。箱にボールが入っていればいるほど入れ替えのコストが大きくなる」という問題設定を思いつきました。そして問題として成立するように試行錯誤し、競プロ部の部員の意見も取り入れながら今の問題になりました。
想定解法は考察さえ出来れば10行ほどの実装で済むものとなっています。複雑なアルゴリズムやデータ構造の知識は不要で考察さえ出来れば解けるという問題になっており、個人的にもお気に入りの問題になりました。
色々な方から面白かったという感想をいただけ、非常に嬉しかったです。
この記事では紹介しきれませんでしたが、他にも面白い問題がありますので是非ご覧になってください。問題はこちらのリンクから、問題の解説はこちらのリンクから閲覧することが出来ます。
おわりに
前回に引き続き、今回もコンテストの作問作業の進行管理を担当しました。試行錯誤しながら問題を準備し、競プロ部員と議論しながら一つのコンテストを作り上げるのは一筋縄ではいかず苦労することも多いです。しかしその分、参加者の感想や懇親会で楽しんでいただけている様子を見ると非常に達成感があります。
フォルシア競プロ部では今後もゆるふわオンサイトの開催を継続していきたいと考えていますので、是非ご参加ください！
また、フォルシアでは大学対抗プログラミングコンテストICPCの国内予選や女性向けプログラミングコンテストCodeQUEENへのスポンサー活動で、競技プログラミングに取り組む皆様を応援しています。
これらのイベントでフォルシアのブースを見かけたら、ぜひ声をかけてみてください！
城武 秀祐
2024年新卒入社エンジニア
学生の頃、ゆるふわオンサイトに参加したことがきっかけでフォルシアを知りました。
フォルシアではフォルシアに興味をお持ちいただけた方に、社員との面談のご案内をしています。
採用応募の方、まずはカジュアルにお話をしてみたいという方は、お気軽に下記よりご連絡ください。
※ 弊社社員に対する営業行為などはお断りしております。ご希望に沿えない場合がございますので予めご了承ください。
