こんにちは！会計チームで開発をしているtakuです。
freeeにはオフカツという、いわゆる社内部活動があります。 今日はその中の一つ、『競技プログラミング部』が実施した社内プログラミングコンテスト (2回目) についてお話しします。
1回目のコンテストの記事はこちら developers.freee.co.jp
事前準備
オンラインジャッジシステムは1回目のコンテストの際に構築されていたので、今回の事前準備は作問とテストがメインでした。
Writerは4人で、合計6問作成しました。
私は今回Writerに初挑戦しました。作った問題はこちらの2問です。
引っ越し
問題
五反田から大崎に N 個の荷物を送ります。
1 回の輸送で最大 M 個の荷物を運ぶことができます。全ての荷物を送るのに必要な輸送の最小回数を出力してください。
コメント
コンテストのとっかかりとして解きやすいものを作りました。
あと最近オフィスが移転したのでその辺りとも絡めました。
あいまい検索
問題
会社の名前が N 個、検索文字列が Q 個与えられます。
各々の検索文字列に対して、与えられた全ての会社名のうち、その検索文字列を名前に含む会社の件数を出力してください。
制約：
- 1 < N,Q < 105
- 会社名は6文字以内
コメント
普通にやると O(NM) かかってしまうけど、会社名が6文字以内と短いのでうまいことすれば何とかなる感じにしました。
問題全体として競技プログラミング頻出のアルゴリズムをバランスよく組み込んだものにしました（貪欲法、動的計画法、いもす法、etc...）
コンテストの約1週間前には全ての問題が揃いましたが、そこからのテスト工程もなかなか難儀でした。
- 言語によってはメモリが想定より多くなり、ジャッジサーバーのデフォルトスペックだと想定解が通らない
- コンパイラ言語での愚直解を落とし、スクリプト言語での想定解を通せる適切な実行制限時間の選定
- 嘘解法潰し
などなど。
作問を経て色々学びはありましたが、特に「高速な言語だと愚直解が通ってしまうケース」のハンドリングは注意せねばなと思いました。自分の場合、競技プログラミングではPythonばかり書いており、まだ手に馴染むコンパイラ言語を持ち合わせていなかったのも足枷になりました。
競技プログラミングをかじる人間として、やっぱりC++を書かなきゃ...と感じました。
コンテスト開始
コンテスト開始です。
本コンテストは、問題数や点数の傾斜など、多分にAtCoderのコンテストを参考にしたものとなってます。
しかし、できるだけ多くの人たちに参加してもらいたいという気持ちから、思い切って以下のような形式をとりました。
- コンテスト期間：7日間としました。通常この手のコンテストは長くても120分くらいなので、だいぶゆったりです。
- 誤答ペナルティ：なし。期間中は何度でも提出でき、間違っても減点ペナルティはありません。
速く正しく回答することに対するインセンティブこそ多少犠牲にはなるものの、忙しい方や、プライベートの都合で特定の時間帯に参加できない人にも参加してもらえることを優先してこの形式を採用しました。
運営は管理画面で回答コードを見ることができます。
特に自分が作った問題に関しては誰がどんなコードを書いてくれたのか気がかりで、期間中はずっと回答コード一覧を更新していました。
がっちり想定解のコードを書いてくれて気持ちが通じ合ったかのような喜びを覚えたり、想定していなかった別解アルゴリズムが通っていて「そんなやり方もあるのか」と勉強になったり、見ていて飽きなかったです。
最終的なコンテスト参加者は32名でした。前回コンテストの参加者数13名から倍以上に増えました。参加ハードルを下げたのが功を奏しました。
そしてなんと3名もの方が全問完答を達成しておりました！
ちなみに提出言語の割合はこちら
解説
コンテスト終了後には解説放送も行いました。 作問者が各々ホワイトボードを用いて、解き方や用いられたアルゴリズムに関する解説を各々行うやり方で進めました。
別途議論用のSlackスレッドも設けました。
コンテスト開催期間中は問題に関する議論を禁じていたので、ここにきて初めてみなさんがどのように考えて問題に取り組んだかがわかりました。
それを見聞きするのもまた面白かったです。
おわりに
競技プログラミングはずっと解く側でしたが、今回作る側が経験でき、新しい楽しみ方を知ることができたのはよかったです。
freeeにこれだけ競技プログラミングを嗜む人がいたのも驚きでした。次回は作問をやりたいと言ってくれた方が何人かいたので、今度はまたチャレンジャーとして楽しめたらなと思います。
