tsutaj です。今回は競技プログラミングの解説記事ではなく、競技プログラミングに関するアプリケーションのリリースノートを書きます。
Competitive Programming Team Maker
ユーザーのレーティングと所属を元に、以下の条件をできるだけ満たしつつチーム分けを行うアプリケーション "Competitive Programming Team Maker" を開発しました。まだ機能が不十分なので beta 版として公開しています。
- チーム間の実力差をなるべく小さくする
- 同一のチーム内で所属の重複がないようにする (同じチームは、できるだけ異なる所属同士で組む)
ユーザー情報を記載した CSV ファイルをインポートすることによって、簡単にチーム分けを実行することができます。また CSV ファイルを持っていなくてもブラウザ上でテーブルを編集・保存することができ、さらにチーム分けの結果も保存することができます。
簡単に使い方を見ていきましょう。例えば、以下のように CSV をインポートします。インポートした CSV はブラウザ上で簡易的に編集が可能ですし、その状態をエクスポートすることもできます。実質 CSV エディタ
これでチーム分けを実行すると、所属が重複する場合もありますが・・・
何度か繰り返すと、所属が重複しない実力差が少ない割当が得られます*1。
有志で開催されている競技プログラミングの合宿である ACPC や RUPC では、その場に集まったメンバーから 3 人を基本としたチームを編成する必要があります。この際に上の条件をできるだけ満たしながらチーム分けをする必要があるのですが、今までは人力でいい感じに行っていました。最近では参加人数が増えてきて人力で行うのが厳しくなってきたため、自動化できないかなあと思い開発した次第です。
使用しているアルゴリズム
詳しくは アプリケーションの About ページ を参考にしていただきたいのですが、ざっくりというと「チーム内のメンバーのレーティング値の二乗和平均」の分散を最小化するような焼きなまし法を行っています。私自身が焼きなまし法初心者であるため、現状のアルゴリズムは改善の余地が割とあると思っていますので、もしも改善案があれば私までご連絡いただければと思っております。
今後実装する予定の機能
詳しくは GitHub の Issue を参照していただきたいのですが、今後実装する予定の主な機能は以下の通りです。GitHub の Issue に記載されていない問題であって、バグや脆弱性・機能の改善点がございましたらぜひ私の Twitter までご連絡ください。
- 焼きなまし法のステップ数やチームの基本人数など、パラメータをユーザー側が調整できるようにする
- 条件を満たさないような書式で入力フォームが埋められていた場合、「チーム分けを実行」ボタンを押せないようにする
- 実行結果を保存した JSON ファイルをインポートすることによって、今まで行ったチーム分けの中で同じチームに配属されたメンバー同士を異なるチームに配属するような仕組みを作る (これは、例えば合宿の Day1 と Day2 で同じチームに属してしまう問題の解消のために実装する予定です)
実装に使用した言語
ここからは開発の裏話的なお話になりますが、実装に使用した言語などを紹介したいと思います。なぜかはわかりませんがこういう情報を公開している開発者が少ないなあと感じるので、せっかくなので書いてみます。
実装には Javascript (jQuery) と PHP を使用しました。理由としてはサーバーサイドで実行される言語を一度も書いたことがなかったためその経験を得たかったことと、API を叩くために PHP が有効であることを聞いたのでそれをつかいたかったからです*2。個人差はあると思いますが、PHP はかなり C++ と似た感覚でかけると思います。むしろ、おそらく C++ よりも便利です。なので競技プログラミングで C++ を日常的に使用している方でしたら特に違和感なく開発できるかと思います。
PHP を勉強するために使用した書籍は プログラミング PHP 第 3 版 (オライリー・ジャパン) ですが、正直に言ってそこまで使用頻度は高くありませんでした。英語のキーワードで Google 検索して Stack Overflow や php.net あたりで情報を得たほうが速いので、適当にネットを検索するほうがストレスなく開発できると思います。ただ、さすがに何も知らない状態で Google 検索するのは不可能だと思うので、最低限の知識は予め身につける必要があると思います。私の場合も GET や POST・セキュリティ周りを何も知らなかったため、このあたりは流石に書籍を参考にしてある程度まで体系的に勉強しました。まだ不十分ではあるのですが・・・
お問い合わせ先
Contact ページ にも記載しましたが、問い合わせたい内容がありましたら tsutaj の Twitter までご連絡ください。開発初心者なのでどのような内容でも大歓迎です！よろしくお願いします。
