"Competitive Programming Team Maker" の beta version を公開しました

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 までご連絡ください。開発初心者なのでどのような内容でも大歓迎です！よろしくお願いします。

*1:アルゴリズムの改善案がありましたらぜひご連絡ください！

*2:実際にはスクレイピングで事足りたため、API はどこにおいても使用していません・・・

Codeforces AIM Tech Round 5 F: Make symmetrical

問題概要

原文 → Problem - F - Codeforces

以下のクエリを処理せよ。なお、以下で考慮する座標はすべて自然数座標である。

1. 点集合に を追加する
2. 点集合から を削除する
3. 点 が与えられる。その時点の点集合について、原点 と を結んでできる直線に対して線対称になるために追加すべき点の個数を求める

解説

まず重要な考察として、ある点 について考慮する際に と原点を通るような円周上で を管理するということが必要です。これは、ある 2 点 と が原点を通るような直線を軸に対象であることと、 と が同一円周上に存在することが必要十分であることによります。

以下の説明では、クエリで扱われる点の座標が であるとし、直線 に対して対称な点のペアがいくつあるかを管理する と、直線 上に点がいくつあるかを管理する を使用しています。

クエリ 1

追加される点は、円 の周上に位置します。原点と を通る直線 に対して をインクリメントし、また同一円周上に存在する他の点 それぞれに対して、原点と を通る直線 に対して をインクリメントすればよいです。

クエリ 2

クエリ 1 とほぼ同様の方針で処理します。対応する と に対してデクリメントすれば良いです。

クエリ 3

直線 に対してクエリに答えるものとし、クエリが呼び出された時点で点が 個存在するとします。すでにペアになっている点対が ペアあり、直線状に位置する点が 個あるため、答えは になります。

最後に、計算量を確認します。クエリ 1 及び 2 で同一円周上に位置する点全てについて操作が必要ですが、実は同一円周上に位置する点の数は十分小さいです。詳しくは Pi hiding in prime regularities - YouTube などをご覧ください (この資料は hsjoihs さんから教えていただきました。ありがとうございます)。円周ごとに独立に管理することで十分高速に処理できます。

ソースコード

直線を管理するために座標を適宜正規化して管理します。クエリで与えられる点は第一象限に属することが保証されているので、比較的容易に記述できます。

pair<int, int> normalize(int x, int y) {
    int g = __gcd(x, y);
    return make_pair(x/g, y/g);
}

signed main() {
    int Q; scanf("%lld", &Q);
    map< int, set< pair<int, int> > > points;
    map< pair<int, int>, int > cnt, on_seg;
    int whole_points = 0;
    while(Q--) {
        int t, x, y; scanf("%lld%lld%lld", &t, &x, &y);
        int sum = x*x + y*y;
        if(t == 1) {
            if(points.count(sum)) {
                for(auto p : points[sum]) {
                    int px = p.first + x;
                    int py = p.second + y;
                    cnt[normalize(px, py)]++;
                }
            }
            on_seg[normalize(x, y)]++;
            points[sum].emplace(x, y);
            whole_points++;
        }
        if(t == 2) {
            on_seg[normalize(x, y)]--;
            points[sum].erase(make_pair(x, y));
            whole_points--;
            for(auto p : points[sum]) {
                int px = p.first + x;
                int py = p.second + y;
                cnt[normalize(px, py)]--;
            }
        }
        if(t == 3) {
            auto line = normalize(x, y);
            int ans = whole_points - 2 * cnt[line] - on_seg[line];
            printf("%lld\n", ans);
        }
    }
    return 0;
}

Codeforces Round #527 Div.3 E: Minimal Diameter Forest

問題概要

原文 → Problem - E - Codeforces

頂点からなる森が与えられる。このグラフに対して辺を追加して木を作りたい。木の直径が最小になるように辺を追加した時の、その直径の値と追加すべき辺を列挙せよ。

解説

森を木に分割して、木同士をマージすることを考えます。木 と をマージする際にどの頂点を選択するかが問題ですが、これは木 の中心 と木 の中心 の間を接続するのが最適です。木 の直径を と、中心からの距離最大値 (つまり半径) を とします。 についても同様に を定義します。このように接続することで、マージされた後の木の直径は となります。

中心同士を順に接続していくことになりますが、中心の頂点のみからなるグラフはどのような形をしていればよいでしょうか？直径を最小化するには、スターグラフにように接続することが最適です。また、元の木において直径が最大になるものをスターグラフ中の次数が多くなる頂点に割り当てることで、最適なマージが可能になります。

ソースコード

vector<int> G[1010];
int N, M, used[1010];

void dfs(int cur, vector<int> &dist) {
    for(auto to : G[cur]) {
        if(dist[to] >= 0) continue;
        dist[to] = dist[cur] + 1;
        dfs(to, dist);
    }
}

pair<int, int> get_graph_info(int id) {
    vector<int> d0(N, -1), d1(N, -1), d2(N, -1);
    d0[id] = 0; dfs(id, d0);

    // 直径は p1 と p2 をつなぐパスになる
    int p1 = max_element(d0.begin(), d0.end()) - d0.begin();
    d1[p1] = 0; dfs(p1, d1); // d1 は p1 からの距離を記憶したもの
    int p2 = max_element(d1.begin(), d1.end()) - d1.begin();
    d2[p2] = 0; dfs(p2, d2); // d2 は p2 からの距離を記憶したもの
    int diam = d2[p1];

    int mi = INF, res = -1;
    for(int i=0; i<N; i++) {
        if(d1[i] < 0 or d2[i] < 0) continue;
        used[i] = true;
        int tmp = max(d1[i], d2[i]);
        if(mi > tmp) mi = tmp, res = i;
    }
    return make_pair(diam, res);
}

signed main() {
    scanf("%lld%lld", &N, &M);
    
    for(int i=0; i<M; i++) {
        int u, v; scanf("%lld%lld", &u, &v);
        u--; v--;
        G[u].push_back(v);
        G[v].push_back(u);
    }

    // (直径, 中心となる頂点)
    vector< pair<int, int> > cand;
    for(int i=0; i<N; i++) {
        if(used[i]) continue;
        pair<int, int> info = get_graph_info(i);
        cand.push_back(info);
    }

    sort(cand.rbegin(), cand.rend());
    vector< pair<int, int> > edges;
    for(int i=1; i<cand.size(); i++) {
        int u = cand[0].second, v = cand[i].second;
        edges.emplace_back(u+1, v+1);
        G[u].push_back(v);
        G[v].push_back(u);
    }

    pair<int, int> whole = get_graph_info(0);
    printf("%lld\n", whole.first);
    for(auto e : edges) {
        printf("%lld %lld\n", e.first, e.second);
    }
    return 0;
}

本番ではスターグラフにする発想が思い浮かばず。冷静に考えれば自然な発想なので、もっと絵をかいてやるべきでした。