6月4日（土）にプロコンを実施したので、それについてつらつらと書いていきます。問題の内容と解説は4日の記事で既に公開しています。

流れ

• ジャッジシステムを作成していて、だいたい動くのが見える。
• 問題の内容が決まる。
• テストデータを作る。
• 非公開のシステムを作り、全体の動きを確認する。
• 予想外に仮想化などで遅いので、制約を見直す。
• コンテスト9日前：ここまで自宅LAN内で実施していたが、本番環境としてまずは自分しか見られない状態で今回のシステムでの最小構成（マスター1台＋ジャッジサーバー2台）をデプロイ。
  • 使用予定のVPSは以前 nexted VT をサポートしているとしていたが、現在はしていないことが判明。予想外に実行時間が遅いため制限時間の見直し
  • 当日の問題で正解のプログラムを提出して確認
• コンテスト7日前：問題ないと判断し、コンテスト日時を決定。テスト用ユーザーなどを削除して公開。
• コンテスト6日前：ジャッジサーバ増設。3台に
• コンテスト2日前：ジャッジサーバ増設。余裕を見て10台に。
• コンテスト開始0分後：Standings に表示されないように細工されたアカウントで動作を確認。提出の要素などを確認する。
• コンテスト開始約25分後：B問題で提出が出始めるが、正解者が出ないことを確認。調査開始。
• コンテスト開始約30分後：Javaでの提出について、クラス内でクラスを定義すると動作しない仕様（お知らせなどでは「Main.java としてビルドされ、 Main.class のみをコピーして実行します。」）が想定しない障壁となっていることを確認。ただし、C++のコードでも通過しないコードがあることを確認。
• コンテスト開始約40分後：B問題で正解すべきと思われるコードを手元で実行した結果などから、最終的に制約を満たしていない入力データがあることを確認。すぐには修正できないと判断して当該テストデータを削除して再ジャッジ。
• コンテスト開始45分後：B問題のリジャッジを告知。
• コンテスト開始58分後：Javaの仕様に対し、不公平にならないと判断した範囲でお知らせを追加。
• コンテスト開始75分後：B問題のジャッジミスの対応（コンテスト延長・開始50分後までのミスの取り扱いの変更）を決定しお知らせを追加。
• コンテスト開始100分後：コンテスト終了。ジャッジ完了を確認した後、告知した措置を反映した Standings を作成。
• コンテスト開始105分後：告知した措置を反映させた Standings を表示。
• コンテスト開始109分後：告知した措置の反映漏れを修正した Standings を表示。

ふりかえり

• テストデータに不備があり、さらに不備の内容が「制約を満たしていない」であったためにプログラム自体は動作し、当日まで気が付かなかった。テストデータの作成は慎重を期すべきであるとともに、なるべく複数人で検証すべき。
• 実行時に何か起こっても TLE 以外は WA 扱いになる仕様が想定外のところで仇に。仮想化に伴う仕様だが、この仕様は修正されるべきである。
• Main.class のみをコピーする仕様もよくない。しかも、そのような状況であっても WA 以外の情報が得られないのは大変よくない。そもそも、あまり想定していないのであれば思い切ってJavaを最初から利用できないようにするなどの対策が必要だった。
• 競技規約に連絡先は書いていたが、上述の問題にもかかわらず問い合わせが来なかったので、問い合わせは（特に今回のような勝手がわかっていない中での実施の場合は）フォームを準備するなどもっと容易にできるようにすべき。
• 参加者は21名と、予想よりやや多い程度だったものの、それでもジャッジサーバーは明らかに10台も要らなかった。ただ、今回発生したリジャッジのような事態も想定すると、スケーリングさせられないなら少なすぎるよりは無駄になるほうがよい。
• Standings に反映されない、自分用アカウントを用意するかは迷った上で用意したが、これはあったほうがよい。
• 色々大きな問題はあったものの、ジャッジサーバが止まるようなことがなかったのはよかった。

その他、Twitter にて公開で寄せられた要望は以下の通り。

• Languageの選択が記憶されるようにしてほしいです！(@machyさん)
• c++でstd::tupleをつかったら通らなかったのでpairに直して解きました。tuple使えるとうれしいです。(@nekomimimiさん)

感想

ジャッジサーバのプログラム作成、問題やテストデータの準備、当日の運営に至るまで一人で実施しました。何はともあれ一通り経験できたのは楽しかったです。とはいえ、不手際が色々あり、せっかくご参加いただいた方にご迷惑をおかけしてしまいました。

ジャッジサーバの準備はなかなかに大変でしたが、目立たないところでテストデータの準備もなかなか大変で神経が磨り減るところでしたし、それでも今回重大なミスが発生した点でもあります。

ジャッジシステムそのもののことはこの後で書きますが、端的に言えば仮想化でジャッジサーバを構築する試みは、ある程度うまくいきそうに見えたものの、やはり無理があるのでコンテナ技術をベースにすべきだと感じています。

なかなかに大変なのは事実ですが、とはいえ学びがあったことも事実です。次回実施することがあるかどうかは現時点ではわかりませんが、実施するとしたら、あるいは何らかの何かを手助けするとしたら、今回明らかになった問題点を解消してよりよいものを作っていきたいと思います。

最後に、21名の参加者の方、ありがとうございました。

ジャッジサーバについて

今回用意したジャッジサーバのシステムについて、簡単な説明を書いておきます。使うための説明などは、もう少しAPIの仕様が定まったりして使いやすくなってからのほうがよいかな、と思っています。

今回はシステム構成について触れた後、 fuzetsu の仕組みのみ紹介しています。

システム構成

• fuzetsu: ジャッジサーバの基盤エンジンです。与えられたソースコードをビルドしたものを安全に実行し、与えられた入力に対する結果を返します。OSv に対して fuzetsu のために最低限必要な修正を施した osv-fuzetsu が必要です。
• flamehaze: 後述の flamehaze-outlaw からソースコードをダウンロードし、前述の fuzetsu を利用して結果を得て flamehaze-outlaw に返すプログラムです。これがジャッジサーバ1台に対し1インスタンス常時起動することになります。なお、 TLE などに関しては失敗時に別のマシンで再実行し、それでも失敗する時のみ正式に失敗とみなす仕組みが flamehaze, flamehaze-outlaw にまたがって備わっています。
• flamehaze-outlaw: ジャッジシステムの中心部で、各種情報を管理する WebAPI を提供します。MySQL とデータをやりとりし、 flamehaze-outlaw の要求に応じてジャッジが必要なソースコードやジャッジ結果をやりとりし、後述の outlaw-ui の問い合わせに応じて必要な情報を返します。
• outlaw-ui: flamehaze-outlaw に接続し、コンテスト参加者に対して WebUI を提供します。

fuzetsu について

与えられた任意のソースコードを安全に実行するシステムです。

現時点では、コンパイル時には gcc の場合に include したファイル一覧を表示するオプションを用い、ホワイトリスト方式でおかしなファイルを include していないか判定を行っています。

実行時には、与えられたファイルを OSv の仮想マシンを用意し、ネットワークから遮断してコンソール経由で入出力を行っています。そのため、仮想マシンイメージをビルド時に作成し、毎回コピーして実行しています。

OSv は仮想マシン上で一つのアプリケーションを動作させることを目的とした Cloudius Systems による OS で、通常 OS が担う機能をハイパーバイザ側に任せています。とても軽量で、 Hello, World 程度のプログラムを読み込んでいる場合、環境によっては、 OS を起動開始してからシャットダウンが完了するまで1秒以内で完了します。開発途上ですが、詳細はオンラインで検索すれば情報が出ると思います。

この仕組みにより、少なくとも任意プログラム実行に関しては、 OS 側での攻撃手段を逐一防ぐ必要がなく、 qemu に渡すオプションで包括的に防ぐことが可能になりました。

一方で、この仕組みのため、使用するVPSで仮想化支援が使えない（nested-VTが使えない）のは大きな問題でした。

また、シリアルコンソール経由でしか情報がやりとりできないため、実行時エラーをほとんど検出できない問題もありました。当初はメモリ使用量を検出する試みもありましたが、「Hello, World だけで 70MB 以上使用するので、メモリ使用量を計測できているうちに入らない」という判断をしました。

現状

ひとまず以下の点は特に改善が必要と考えています。

• fuzetsu は仮想化ではなく、コンテナをベースとすべきである。
• WebAPI の URL が .php なのは今後の互換性などの観点でよろしくないのと出力形式も行き当たりばったりなので、修正して自然言語で明示する。

おわりに

コンテストを実施したときのことをつらつらと書いてきましたが、開催側に回って初めてわかることは多いので、形はどうあれ実施してみることをお勧めします。その障壁を下げるためのジャッジシステム公開については今後努力します。

2016年6月4日 21:00から、プログラミングコンテスト「にろきプロコン#1」を実施しました。

まずは、問題の内容と想定した解法を記します。

実施に至っての色々や途中でミスが発覚して色々大変だったことの公開や、ジャッジ用のソースコード公開はこの土日の間に公開する予定です。

A. ふぃずばず

問題

FizzBuzzといえば、聞いたことがある方も多いのではないでしょうか。
大まかに説明すると、次のルールで1から順番に数を読み上げていくゲームです。

• 原則として数をそのまま読み上げる。
• ただし、3で割り切れる場合は数を読み上げずに Fizz と言う。
• 5で割り切れる場合は数を読み上げずに Buzz と言う。
• 3でも5でも割り切れる場合は、上のいずれにも従わず、FizzBuzz と言う。

順番に読み上げるのは飽きてしまったので、 FizzBuzz にランダムアクセスすることにしました。番号を与えられたとき、その番号に相当する読み上げるべきものを出力してください。

Input

N
i1
i2
...
iN

1行目に、テストケースの数Nが書いてあります。
2から(N+1)行目には順にそれぞれ読み上げるべき番号が書かれています。

Output

o1
o2
...
oN

N行それぞれに、書かれた順に入力された番号で読み上げるべきものを書いてください。最後の行にも改行が必要です。

制約

1 ≤ N ≤ 1,000
1 ≤ i_1..N ≤ 1,000,000

Sample Input

5
1
3
413
55
1500

Sample Output

1
Fizz
413
Buzz
FizzBuzz

解説

順に入力し、それぞれを「15で割ったあまりが0かどうか」「5で割ったあまりが0かどうか」「3で割ったあまりが0かどうか」で条件分岐します。

ソースコードは例えば以下のようになります。

#include 

using namespace std;

int main(){
	int T;

	cin >> T;

	for (int i = 0; i < T; ++i) { int n = 0; cin >> n;

		if (n % 15 == 0) {
			cout << "FizzBuzz" << endl;
		} else if (n % 5 == 0){
			cout << "Buzz" << endl;
		} else if (n % 3 == 0){
			cout << "Fizz" << endl;
		} else {
			cout << n << endl;
		}
	}

	return 0;
}

B. 郵便係

問題

あなたは、郵便物を配送する仕事につきました。
今日も一仕事を終えて拠点に戻ってきましたが、トラックの荷室の奥に一つだけ、配達時間帯指定つきの荷物が残っていることに気付きました。
この荷物を時間内に配送する必要がありますが、トラックが出した最高速度が従業員評価に組み込まれているため、最高速度をなるべく抑えないといけないことを思い出します。トラックは自動運転になっており、速度を指定すると指定した速度で走行しますが、赤信号でのみ停止します。
そのため、なるべく低い速度を指定しつつ、その荷物を指定時刻までに届ける必要があります。幸いなことに、この道はよく通る道で、信号の動きを完璧に把握していますし、それ以外の要因で指定速度より低くなることはありません（加速や減速に要する時間も無視できます）。
この問題を解決するため、配送に使える残り時間（秒）、目的地までの距離（m）、トラックに指定可能な最高速度（m/秒）、各信号の位置と動きを入力（後述）したとき、指定する必要がある速度（m/秒）の最低値を整数で答えるプログラムを書いてください。速度は整数でしか指定できないので、小数で結果が得られたとしても切り上げて回答してください。ただし、トラックに指定可能な最高速度でもなお時間内に到達できない場合は-1と答えてください。
信号の挙動：出発してからx秒後に、この信号は初めて青になります。青になったら、y秒ごとに青と赤を切り替えます。つまり、x+y秒後に赤信号になり、x+2y秒後に再び青になって進むことができるようになります。なお、xはマイナスになることもありますが、その場合も出発後x秒後に青信号になり、その後y秒ごとに信号が切り替わります。

Input

time distance speedlimit
N
location1 x1 y1
...
locationN xN yN

1行目：指定所要時間（秒） time、目的地までの距離（m） distance、トラックに指定可能な最高速度（m/秒） speedlimit が順にスペース区切りで入力されています。
2行目：信号の数(N)が入力されています。
3から(2+N)行目：信号の位置（拠点からの距離；m） location_i、問題文中の信号のパラメータx_i, y_i がスペース区切りで入力されています。

Output

speed

結果は一行で、問題に問われている速度（m/秒で整数、ただし到達できない場合は-1）を出力してください。改行が必要です。

制約

1 ≤ N ≤ 100
1 ≤ time ≤ 100,000,000
1 ≤ distance ≤ 100,000,000
1 ≤ speedlimit ≤ 100,000,000
1 ≤ location_1..N ≤ distance
1 ≤ y_1..N ≤ time
-y_i ≤ x_i ≤ y_i for i in 1..N
location_i-1 ≤ location_i for i in 2..N

Sample Input

600 6000 20
3
100 10 20
400 0 30
600 10 45

600 5900 10
1
100 120 200

Sample Output

11

-1

二つ目の例では、5900m離れたところまで600秒で配送する必要があります。最初の信号が100m離れた地点（残り5800m）にありますが、どんなに速く移動してもここを通過できるのは120秒後ですから、480秒しか残らず、最高速度を以てしても残りの5800mは走破できません。

解説

目的地までの距離と時間がわかっていますが、途中に待ち時間が一定でなく、一定のタイミングまで待たされる信号がたくさんあります。それらは独立して動いているので、一度にすべての要因を考慮するのは難しそうです。
信号の数は100程度しかないので、速度を決めたときにシミュレーションを行って所要時間を計算することはできそうです。
また、信号は早くついても一定のタイミングまで待たされるだけなので、速度を上げたことによって所要時間が伸びることはありません。つまり、ある速度で間に合わなかった場合は、必ずそれよりも速度を上げなければならないということです。
この性質を利用し、二分探索で解くことができます。例えば、以下のようになります。なお、浮動小数点の誤差の問題を回避するため、以下のコードでは時間は速度を乗じた状態で保持しています。

#include 
#include 

using namespace std;

int inside_loop(long long arrive, long long speed, long long x, long long loop) {
	long long arrive_clock = arrive % (2 * loop * speed);
	if (arrive_clock < x * speed) {
		arrive_clock += loop * speed * 2;
	}

	return arrive_clock < (x + loop) * speed;
}

int main(){
	long long t, d, s, N;
	vector  l, x, y;

	cin >> t >> d >> s >> N;

	for(long long i = 0; i < N; ++i){ long long tl, tx, ty; cin >> tl >> tx >> ty;

		if (tx < 0) {
			tx += 2 * ty;
		}

		l.push_back(tl);
		x.push_back(tx);
		y.push_back(ty);
	}

	l.push_back(d);
	x.push_back(0);
	y.push_back(t + 1);

	long long lo = 1;
	long long hi = s + 1;

	while (lo < hi) {
		long long mid = (lo + hi) / 2;

		long long curpos = 0;
		long long arrive = 0;

		for (long long i = 0; i < l.size(); ++i) { arrive += l[i] - curpos; if (! inside_loop(arrive, mid, x[i], y[i])) { arrive = ((arrive - x[i] * mid + (2 * y[i] * mid) - 1) / (2 * y[i] * mid)) * (2 * y[i] * mid) + x[i] * mid; } curpos = l[i]; } if (arrive > t * mid) {
			lo = mid + 1;
		} else {
			hi = mid; 
		}
	}

	if (lo > s) {
		cout << -1 << endl;
	} else {
		cout << lo << endl;
	}
}

C. 郵便係・続

問題

インターネットを構成する要素としておなじみの IP (Internet Protocol) では、 IP アドレスを元にパケットを目的地に配送します。
例えば家のLANに繋がっているパソコンの場合、LAN内は直接通信できるので直接配送し、LANの外であればデフォルト・ゲートウェイに渡してそこから先の配送を任せます。複数のネットワークに繋がっていれば、宛先によって適切な送り先に渡すことになります。宛先の判定は色々な方法がありますが、この問題ではとてもシンプルなルーティングテーブルを考えます。

今回考えるルーティングテーブルは、次のようなエントリがたくさん集まっています。

<ネットワークアドレス> <ネットマスク> <宛先インターフェイス> <優先度>

具体的には例えば以下のようになっています。

ネットワークアドレス	ネットマスク	宛先インターフェイス	優先度
0.0.0.0	0.0.0.0	gateway1	20
192.168.1.0	255.255.255.0	eth0	10
192.168.1.0	255.255.255.0	eth1	20
192.168.1.128	255.255 255.128	eth2	30

IPアドレスとネットマスクは、8ビットごとに区切って書かれていますが、実際には32ビットで一続きです。たとえば、 1.2.128.129 は 0x01028081 とも表現できます。
各パケットの宛先IPアドレスと、ルーティングテーブルのエントリのネットマスクの論理積（ビット演算でいう&）がネットワークに一致すれば、そのエントリの宛先インターフェイスがパケットを届けるべきインターフェイスとなります。ただし、複数ある場合は、

• ネットマスクが大きい順
• ネットマスクも同じ場合は優先度の数字が小さい順

に優先します。

たとえばこの例では、 192.168.1.1 宛なら eth0 に、 192.168.1.130 は eth2 に、 10.0.0.1 宛や 240.0.0.1 宛なら gateway1 に届けます。
実際にはgatewayはインターフェイスではなくて、もう少し情報が書いてあって結局ethのどれかに投げることになるな、と思っている方もいるかと思いますが、ここではgatewayのままにすることにします。

郵便配送の経験を積んだあなたはこのパケットを分配する仕事につきましたが、毎回ルーティングテーブルを目で見て判定するのは効率的でないことに気付きました。仕事を楽にするため、ルーティングテーブルと、パケットの宛先がいくつか入力された時、それぞれのパケットの宛先を出力するプログラムを書いてください。なお、IPアドレスはピリオド区切りではなくスペース区切りで与えられます。

Input

N
network1 netmask1 interface1 metrics1
network2 netmask2 interface2 metrics2
...
networkN netmaskN interfaceN metricsN
M
ipaddr1
ipaddr2
...
ipaddrM

N, M は整数で、 IPそれぞれルーティングテーブルのエントリの数、パケットの数を示しています。
network, netmask, interface, metrics はそれぞれネットワークアドレス、ネットマスク、宛先インターフェイス、優先度を示しています。
ipaddr は、各パケットの宛先IPアドレスを示しています。
network, netmask, ipaddr はそれぞれ0から255までの整数4つで表現されています。

Output

interface1
interface2
...
interfaceM

M行にわたり、それぞれの行に順番にそれぞれのパケットの宛先のインターフェイス名を書いてください。最後の行にも改行が必要です。

制約

• interfaceは10文字までの文字列（含む文字は[a-z0-9]のみ）
• 優先度は整数（0から100）
• network, netmask, metrics のいずれもが重複する行はない
• interface が重複する行はない
• netmask で 0 になっているビットに相当する network のビットは 0 （つまり network & (~netmask) = 0 ）
• 必ず一つ以上、 network = netmask = 0 0 0 0 の行がある（つまり、すべてのパケットは宛先がある）。
• netmask は全体を2進数で表現したとき、各ビットについてその左のビットが0ならばそのビットも0である（つまり、2進数で表現すると左側に0個以上の1が並び、残りのビットは0で埋まっている)
• 1 ≤ N ≤ 100
• 1 ≤ M ≤ 100

Sample Input

4
0 0 0 0 0 0 0 0 gateway1 20
192 168 1 0 255 255 255 0 eth0 10
192 168 1 0 255 255 255 0 eth1 20
192 168 1 128 255 255 255 128 eth2 30
7
10 0 0 1
192 168 1 1
192 168 1 123
192 168 1 130
192 168 1 159
192 168 2 12
240 0 0 1

Sample Output

gateway1
eth0
eth0
eth2
eth2
gateway1
gateway1

解説

必要なアルゴリズム自体は公開されており、全てのケースで全探索を行っても計算量も問題にならないため、アルゴリズムが思いつかないというより、ビット演算などの意図を理解して仕様通りにコードを書けるかを問う問題です。

まず、

IPアドレスとネットマスクは、8ビットごとに区切って書かれていますが、実際には32ビットで一続きです。たとえば、 1.2.128.129 は 0x01028081 とも表現できます。

とありますから、4つの区切りを受け取ったらビットシフトを使って一つの32ビット符号なし整数（64ビット整数などでも可）にまとめてしまいましょう。

続いて、一つ一つの宛先について、ビット演算子の「&」を用いて宛先が当てはまるか判断し、ネットマスクの長さと優先度が最も長いものが残るようにして判定を上からしていきましょう。

例えば以下のようになります。

#include 
#include 

using namespace std;

int main(){
	int N, M;
	vector  network, netmask, metrics;
	vector  interface;

	cin >> N;
	for(int i = 0; i < N; ++i){
		unsigned int tnw = 0, tnm = 0, tme;
		string tin;

		for (int j = 0; j < 4; ++j) { int t; cin >> t;
			tnw = (tnw << 8) + t;
		}

		for (int j = 0; j < 4; ++j) { int t; cin >> t;
			tnm = (tnm << 8) + t; } cin >> tin >> tme;

		network.push_back(tnw);
		netmask.push_back(tnm);
		interface.push_back(tin);
		metrics.push_back(tme);
	}

	cin >> M;

	for (int i = 0; i < M; ++i) {
		unsigned int addr = 0;

		for (int j = 0; j < 4; ++j) { int t; cin >> t;
			addr = (addr << 8) + t;
		}

		int bestid = -1;

		for (int j = 0; j < N; ++j) {
			if ((addr & netmask[j]) == network[j]) {
				if (bestid == -1) {
					bestid = j;
				}

				if (netmask[bestid] < netmask[j]) {
					bestid = j;
				}

				if (netmask[bestid] == netmask[j] && metrics[bestid] > metrics[j]) {
					bestid = j;
				}
			}
		}

		cout << interface[bestid] << endl;
	}
}