2020-09-08

AtCoder Library (日本語訳)

AtCoder

Codeforces に投稿されたりんごさんの記事の日本語訳です。
単に ACL の紹介のみにとどまらず、AtCoder のコンテストに使う問題の選び方に関する話など、さまざまな思想を感じとれるものだったので、日本語で広めるのもよさそうだと思って翻訳してみました。

codeforces.com

以下、「本文」の訳文

最近、競技プログラミングにおいて使用されるアルゴリズムやデータ構造は増加の一途を辿っています。それ自体は素晴らしいことです。なぜなら、より多くのアルゴリズムが活用できるならば、出題できる問題の幅が広がり、より多くの問題を楽しめるようになるからです。

一方それによって、コンテストの楽しい部分である「アドホック」「考察する」といった部分に到達するためには、より多くのアルゴリズムの学習に時間を割く必要が生じています。これらは時には煩わしいものです。

たとえば、一般グラフの最大マッチングを求める必要のある問題が出題されることがあります。そのときは、それを解説した論文を探し、それを読み、大変複雑なアルゴリズムを実装する必要があります¹。
他にも、ライブラリの定数倍に気を遣ってチューニングする必要が生じることもあります。
さらには、複数のライブラリを組合せたときの変数名の衝突などにも気を遣う必要が生じることもあります。

今まで AtCoder では、基本的には「予め実装しておいた複雑なアルゴリズム」を必要とする問題はすべて不採用としていました。たとえば AtCoder では、遅延評価つきセグメントツリーを必要とする問題を出題したことはありません。しかしこのままでは、それらの複雑なアルゴリズムを必要とする面白い問題を出題できなくなります。コンテストの問題の幅を制限することになってしまいます。

この問題にどのように対処したらよいでしょうか？この問題を解決する大変よい例が C++ の STL です。STL はたとえば std::set のような非常に複雑なデータ構造を内包しています。これをオラクルとして活用することで、たくさんの処理を実現することができるのです。

同様に私たちは、さまざまなアルゴリズムをオラクルとして使えるように準備することにしました。これによってコンテスト参加者は、問題の面白いところのみに集中することができます。

すべてのソースコードを yosupo が実装し、rng_58, maroonrk, DEGwer がテストを担当しました。コンテスト参加者がこれらをオラクルとして活用できるようにするために、ライブラリの使い方についての詳細なドキュメントも用意しました。たとえば、2 つの配列が与えられたときに、その convolution 積を計算するコードを以下に挙げます:

#include <atcoder/convolution>
#include <cstdio>

using namespace std;
using namespace atcoder;

int main() {
    int n, m;
    scanf("%d %d", &n, &m);
    vector<long long> a(n), b(m);
    for (int i = 0; i < n; i++) {
        scanf("%lld", &(a[i]));
    }
    for (int i = 0; i < m; i++) {
        scanf("%lld", &(b[i]));
    }

    vector<long long> c = convolution(a, b);

    for (int i = 0; i < n + m - 1; i++) {
        printf("%lld ", c[i]);
    }
    printf("\n");

    return 0;
}

見ていただいてわかるとおり、このライブラリをオラクルとして活用することで、大変明快なコードとなっています。このライブラリは AtCoder のサーバーにインストールされていますので、AtCoder コンテストで使うことができます。

ここで、誤解してほしくないことがあります。私たちは「ライブラリ志向の問題」を推進しようとしているわけではありません。

これまで AGC や ARC では「ライブラリパートも含めた実装量に対して考察量がどの程度あるか」という観点から問題を選んでいました。これからは、「ライブラリパートを除外した実装量に対して考察量がどの程度あるか」という観点から問題を選ぶこととなります。ただそれだけのことです。たとえば「セグメントツリーを貼って、その後も長い実装が続く」というタイプの問題はこれからも出題しません。当然ながら、今後も出題する問題の大部分は、ライブラリを必要としない問題となります (以下にアナウンスする ACL Contest は除く)。これまで AtCoder で理念としてきた「実装は簡単に」というルールは今後も踏襲していきます。そればかりか、次代の AtCoder アドミンである maroonrk は、「すべての問題に対して、自身の手で Python で通るコードを書く」とさえいっています。

以下、「リンク集」の訳文

2 回にわたって開催する ACL Contest は、ARC 格の rated コンテストとなります (rated 対象：1200-2799、150 分間)。ただし rated 対象やコンテスト時間を変更する可能性はあります。これらのコンテストでは、想定解において ACL を用いる問題が多く出題されますが、それでもなおメインは考察パートです。ACL に関係のないダミー問題を含む可能性もあります。したがって、「そうか...この問題は ACL を使うのならきっと解法はこうなるに違いない...」というふうには考えないようにしてください。

以下、「Codeforces コミュニティへの相談事項」の訳文

2 つの相談事項があります²。

ACL の初代バージョンは、ほとんどのトップレベルの競技プログラマはすでにライブラリとして持っているような比較的基本的なアルゴリズムのみを含んでいます。そこに「一般グラフの最大マッチング」のような、より高度なアルゴリズムも含めた方がよいでしょうか？その際には Java ユーザーに対して不公平となりうることを懸念しています。
計算幾何についてはどうでしょうか？現状では、数値誤差を取り扱ううえでの、確信を持てるベストな方法を見いだせていないため、含めておりません。