山路です。今回は、僕の趣味である「競技プログラミング」について、少しでも知ってもらおうと開催した、「Fusicプログラミングコンテスト」のレポートになります。

競技プログラミングとは

そもそも「競技プログラミング」というワード自体初めて聞いたという人も少なくないかもしれません。

競技プログラミングとは、「速く、正確に与えられた課題を解決するプログラムを書く」ことを競う知的スポーツです。ここ数年で競技プログラミングの価値は勢いを増し、就活に利用されるまでになりました。毎週末に行われるコンテストでは実に6000人弱もの競技プログラマーがその腕を競い合っています。

Fusicプログラミングコンテストレポート

そういうわけで、Fusicプログラミングコンテストを開催しました。（実際のコンテスト環境としては、 HackerRank というサイトを利用させていただきました。）

作問は全て僕で、全部で5問作りました。難易度は100-100-200-200-300です。今回は７人の方にご参加いただいたのですが、全員がプログラミングコンテストが初めてということなので、アルゴリズムやデータ構造の知識を問う問題は出さず、誰もが「解けた！楽しい！」と思えるような問題になるよう考えました。

それでは以下レポートです。

〜コンテスト開始〜

いよいよFusicプログラミングコンテスト、スタートです。まずはウォームアップの100点問題として、以下の２問を用意しました。

A-Hello, Fusic Procon!

問題
こんにちは！Fusic プログラミングコンテスト 001にご参加くださいましてありがとうございます。
感謝の気持ちでいっぱいです。ところでそんな感謝の気持ちを正の整数a, bとして与えるので、 a + b の計算結果と Hello, Fusic Procon! という文字列を並べて出力してください。

制約
- a, b は１以上10以下の整数

B-i18n Format

問題
i18nとは、「『ソフトウェアを特定の地域の言語、仕様に縛られることなく、世界各国で共通して利用できるようにすること』を意味するinternationalization」を省略して表したものです。
さて、このような「文字列の先頭文字と末尾文字はそのままに、その間を文字数に置き換えることで文字列を省略する記法」をi18n流省略記法と名付けることにしましょう。
英子文字からなる３文字以上の文字列が与えられるので、それをi18n流省略記法で表したものを出力してください。

制約
- Sは英小文字からなる
- Sは３文字以上100文字以下である

皆さん問題というよりも、標準入力やコンテストサイトの使い方に戸惑っていました。数分経つと、「解けた！」「よっしゃー！」という声がちらほらと出るように。皆さん問題をAC（正解）する快感に早速浸かり始めているようでした。プログラミングコンテストにおけるACは、業務でいうなら「数十人のレビュアーに同時にApproveをもらった」かのような快感があるのです。

ウォームアップが終わり、待ち受けるは以下の２問です。

C-Ammonia Prizes

問題
Fusicには技術評価制度への推薦を後押しするための、アンモニア賞というユニークな賞があります。
考案者の納富さん(N)・浜崎さん(H)・萩原さん(H)・濱野さん(H) の頭文字を取って、Nが１つとHが３つ → NH3ということで、この名前がつきました。

さて、20xx年、Fusicの社員はN人となりました。
また各社員は以下のルールに基づき、勝手に第２、第３のアンモニア賞を作り始めました。

頭文字が N の社員１人と、頭文字が H の社員３人で、アンモニア賞を作る。
すでにいずれかのアンモニア賞の作成に携わった社員は、他のアンモニア賞の作成に携わることはできない。
このルールの元、20xx年のFusicにおいて、最大でいくつのアンモニア賞が誕生するかを求めてください。
ただし、１つのアンモニア賞も作られないようなケースもあることに注意してください。

また、必ずしも現Fusicの社員情報が与えられる訳ではないことに注意してください。

制約
- Nは1以上10万以下の整数
- 各社員の名前は英字からなり、先頭の文字は大文字である

D-Angry Shredder

問題
Fusic社内のシュレッダーはとんでもない速度で溜まっていくことで有名です。
あまりに酷使された結果、ついに自我が芽生えたシュレッダーくんは、「次にゴミの容量がWに達したら爆発してやろう」と決意しました。

さて、あなたはそんなシュレッダーくんのゴミ捨て係に任命されました！ 　　

ゴミ捨て係のあなたは、シュレッダーくんに対して以下の操作を行うことができます。
- シュレッダーに紙をx入れる。　シュレッダーのゴミの容量がx増える。
- シュレッダーの使用後に、ゴミを回収しシュレッダーのゴミの容量を0に戻す。

あなたの目的は、シュレッダーくんが爆発しないように適宜ゴミを回収することです。（最初、シュレッダーくんにゴミは貯まっていません。 ）
ただし１階は地味に遠いので、ゴミを回収する回数は出来るだけ少ない方が望ましいと思っています。

これからシュレッダーが使われる回数N、各回で捨てられる紙の量ai、シュレッダーくんが爆発するゴミの容量Wが与えられるので、最低何回ゴミを回収する必要があるかを求めてください。
ただし、どうやってもシュレッダーくんが爆発してしまう場合には-1を出力してください。

また、ある回で捨てる紙を、複数回に分けてシュレッダーにかけるような操作は許されていないので、注意してください。

制約
- 入力は全て整数
- Nは1以上10万以下
- ai, Wは1以上10億以下

特に速かったのは毛利さん。 20分段階で、４問目までをACし、最終問題へと歩を進めました。

続いて岡嵜さん、濱野さんも続きます。競プロ初体験でこのスピードはいいペースです。

最終問題はE-Fusic Fusion。これまでの４問とは別種の難易度になっています。

E-Fusic Fusion

問題
20xx年、Fusicにマッドサイエンティストが入社してきました。
彼の使命は、社内のエンジニア力X以上の人間の数を最大化することです。

そのためならどんな手段でも厭わない彼は、「Fusic Fusion Machine」を開発しました。このデンジャラスな機械は以下ような機能を持っています。

社員２人をFusic Fusion Machineに詰め込んでスイッチを押す。
すると、詰め込まれた二人のエンジニア力の和を持つ、１人の社員になって出てくる。
ただし、Fusic Fusionで誕生した社員を、再びFusic Fusion Machineに詰めることはできない。
大変便利なFusic Fusion Machineですが、多くのリソースを使うために、 最大でK回までしか動作させることができません。

さて、20xx年の社員数N、 各社員のエンジニア力ai、 マッドサイエンティストが目指すの値X、Fusic Fusion Machineを利用できる回数Kが与えられます。

難しいことが苦手なマッドサイエンティストの代わりに、「Fusic Fusion Machineを最適に利用した場合に、エンジニア力X以上の社員を最大で何人にすることができるか？」を求めあげてください。

制約
- 入力は全て整数
- Nは1以上10万以下
- Kは0以上10万以下
- ai, Xは1以上10億以下

さすがは最終問題ともあって、先行した３人もなかなか正答にたどり着けません。

そうこうしているうちに、Dまで解いた人が増え、「E問題を最初に解くのは誰か」というデッドヒートに発展しました。果たして全完は現れるのでしょうか……！？

最終順位表は以下のようになりました。

惜しくも全完は出ず！

最初に完璧なスタートダッシュを決めた毛利さんの優勝となりました！！！本来ならこの時点でコンテストは終了、解説に移るのですが、「もう少しやらせてほしい」との声が。

急ではありますが、E問題をACするための延長戦が始まりました。 Fusic20の信条の一つ、『諦めが悪い』を見事に体現していますね。作問者としても嬉しい限りです。
結果として全員がD問題までを解ききり、E問題にぶつかっていきました……！

本当に惜しくも延長戦でもEの正解者は出ませんでしたが、皆さんのやり切った顔と、E問題の解説を理解した時の納得した顔がとても印象に残っています。こうしてFusicプログラミングコンテストは大成功で幕を下ろしました。

本当の延長戦

実は毛利さんだけは「絶対に自力で解く」と解説を聞かずに先に帰られていました。そして１度解散した翌日、土曜日の朝、ついに毛利さんがEをACしました……！！！

この熱量に負けないよう、今後も精進を積んで行こうと思いました。

おわりに

コンテストを企画した当初は人が集まるのか、集まったとしても楽しんでもらえるのかと、とても不安でしたが、想像以上に楽しんでいただくことができました。本当に嬉しかったです。遠くない将来に第二回を開催したいですね。参加してくださった方々、並びにこうした企画を気軽に展開できるFusicに感謝です!ありがとうございました！

Fusic Tech Blog

# 競技プログラミング

Fusicプログラミングコンテストを開催しました！