Competitive Programming (2) Advent Calendar 2019 17 日目の記事です。
概要
USACO (USA Computing Olympyad) は、おもに米国の中高生 (pre-college) を対象としたオンラインのプログラミングコンテストです。
USACO で優秀な成績を獲得した生徒は、国際情報オリンピック (IOI) の米国トレーニングキャンプ参加生や、米国代表選手候補になれるため、IOI の日本国内予選である日本情報オリンピック (JOI) の米国版と考えるとわかりやすいです。
キャンプ参加生や代表選手に選ばれる資格を持つのは、米国に住む中高生に限られますが、コンテストに参加するだけなら、誰でもどの国からでも無料で挑戦できます。
日程
USACO のオンラインコンテストは 12 月～ 3 月にかけて 4 回行われ、そのすべてに、どの回からでも参加できます。2019-2020 年の日程（日本とは時差があります）は次のとおりです
- 12/13-16: First Contest
- 1/17-20: Second Contest
- 2/21-24: Third Contest
- 3/27-30: US Open
それぞれのコンテストは金曜日～月曜日の 4 日間に設定されていて、この 4 日間の中から任意の時間を選んで参加できます。休日に用事があったとしても、その前後の日に参加できるという親切な仕組みです。
当然ですが、時間差で問題を解く参加者がいるため、自分が問題を解き終わったとしても、コンテスト期間中はその内容についてインターネット等で発信することはできません。
division
USACO のコンテストは毎回、難易度が低い順に Bronze, Silver, Gold, Platinum の 4 つの division が用意されています。参加者は自分のランクに応じた division に自動的に割り振られます。アカウントを作成したばかりの参加者は全員 Bronze からスタートします。詳しくは後述しますが、スコアに応じて上位の division に挑戦できるようになります。
コンテストのルール
USACO のコンテスト時間は 4 時間が標準です。
各回のコンテストの期間は 4 日間ありますが、問題をオープンした瞬間に、残り時間のカウントダウンが始まるので、睡眠などで離脱せずその日のうちに提出を完了する必要があります。残り時間はページの上部に表示されます。
問題文は英語が標準です。ロシア語やスペイン語、フランス語、中国語などの翻訳が用意されている場合もあります。（日本語は日本人参加者が少ないためありません）
問題の数は、どの division も 3 問（ときどき 4 問）で、部分点ありの 1,000 点満点です。
コンテスト中に提出したコードはすぐにジャッジ結果（テストケースごとの AC/WA/TLE, コンパイルエラーの内容等) が表示され、正解するまで何度もペナルティ無しで提出しなおすことができます。
使用可能なプログラミング言語は 2019 年現在 C, C++, C++11, Java, Pascal, Python 2.7, Python 3.4 です。
ローカルのソースファイルを問題ページからアップロードすることで、解答を提出します。
実行時間やメモリなど、詳細なルールについては各回のコンテストページを参照してください。
サンプルとデータの入出力
問題文には基本的にサンプル入出力が 1 組だけ用意されています。
出力例には、なぜこのような出力が得られるかの説明がついているので、これも重要なヒントになります。
USACO のジャッジシステムにおけるテストデータの入出力は、問題文で指定されたファイル名のテキストファイルを通して行われます。
例えば入出力ファイルとして blist.in, blist.out が指定されている場合、C++ では
#include <bits/stdc++.h>
int main()
{
freopen("blist.in", "r", stdin);
freopen("blist.out", "w", stdout);
int x, y;
std::cin >> x >> y;
std::cout << (x + y) << '\n';
}
のように freopen() を使って標準入出力をファイルストリームに関連付けることで、簡単に対応できます。
division の昇格
全問正解するか、部分点の合計で 1,000 点満点中 700～800 点以上 (コンテストによって異なります）を獲得すると、上位の division に昇格できます (promotion)。
コンテスト期間中であれば、そのまま続けて上位の division に挑戦することができます（残り時間のカウントダウンもリセットされます）。
したがって、理論上は 1 日で Bronze から Platinum まで駆け上がることも可能です。
過去のコンテスト
過去の問題やテストデータ、解答例は Previous Contests からアクセスできます。アカウントを作成してログインした状態であれば、ソースコードを投稿してジャッジ結果を見ることもできます。
参加方法
USACO Web サイト のページ右側にある「Register for New Account」からアカウントを作成します。
高校卒業年度「Graduation Year」には、大学生以上の場合は「9999」を入力します。
国籍「Country」には、日本の場合は「JPN」と入力します。
コンテスト開催中は、USACO Web サイトのトップページに、コンテストに参加するためのボタンが表示されます。それ以外の期間はあまり Web サイトの更新が無く、その年度のコンテスト日程も期日が近くならないと発表されない（今年度は 11 月だった）ので注意しましょう。
USACO のコンテスト問題の特徴
問題文は、Farmer John 氏と、彼が飼う $N$ 匹の牛や $N$ 個の農場に関するストーリーが多いです（AtCoder でいう「高橋君」的存在）。牛たちの中でも、Bessie という名前の Farmer John 氏のお気に入りの牛は、賢いので他の牛を調教したりゲームを発案したりできます。驚かないでください。
おわりに
USACO に日本人が参加しても、IOI 代表選手に選ばれるなどのメリットはありませんが、オンラインで誰でも気軽に参加でき、世界中の何千人もの中高生と競い合え、よく練られた英語の問題を読む練習になります。興味を持ったらぜひ参加してみましょう。
USACO Web サイト: http://www.usaco.org/index.php