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の外であればデフォルト・ゲートウェイに渡してそこから先の配送を任せます。複数のネットワークに繋がっていれば、宛先によって適切な送り先に渡すことになります。宛先の判定は色々な方法がありますが、この問題ではとてもシンプルなルーティングテーブルを考えます。

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

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

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

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;
	}
}

Google Code Jam の2015年の Round 1A のC問題で、格子点との角度を求めて計算をする必要があるような問題がでました。また、他にも格子点が出てきて角度を計算して処理したくなる問題があります。

格子点同士を結んだ任意の二直線の角度差の最小値がわからなかったので考えた結果の覚え書きです。ウェブで探せば既にどこかにありそうな気もしますがまあ。

大きさが l*l になるような格子で格子点を結んだ場合、二つの直線のベクトルをそれぞれ (x₁, y₁), (x₂, y₂) とします。

それぞれは 0 から l までです。

この二つの傾きはそれぞれ y_i / x_i となるので、この二つの傾きの差は

(y₁x₂ – x₁y₂) / (x₁x₂)

となります。格子点なので分子は必ず整数なので、傾きの差は最小でも l^-2 となります。

また、逆数の差も必ず l^-2 あるので、絶対値の差だけでなく相対的な差も l^-2 以上あることになります。

ここで x₁ = x₂ = l の時、分子がlの倍数になってしまい 1/l より大きくなるので、実は l^-2 よりほんのすこし大きくなります。二直線が (l-1, 1) (l, 1) の時、 1 / l(l-1) で最小です。通常その差は意識しないので、以後は l^-2 として行きます。

角度差の最小値については、 0から45度（π/4）までを対象に考えます（他の領域でも計算過程が異なるだけで結果は同じになるはずなので）。

d/dx tan^-1x = cos² (tan^-1 x) はこの範囲で 1/2 から 1 までの範囲で変化するので、角度の差の最小値は l^-2/2 ラジアン、あるいは 90π^-1l^-2 度ということになります。

従って、計算するのに型を決定したりするにあたっては

傾きの計算と結果： 相対誤差または絶対誤差のうち小さい方が l^-2
ラジアンの保存：　絶対誤差が l^-2/2
ラジアンについてのEPSの設定：　l^-2/2 未満

実際には誤差が累積するので、これに対して余裕を持った値ということでしょうか。

なお、doubleは仮数部が52ビットらしいので、20ビットだとラジアンについても累積して41ビットにならなければよいので格子サイズの縦や横が20ビットくらいまで（1e6くらいまで）なら心配する必要はないという感じでしょうか。

変な組み合わせですごく小さな誤差が出るのでは？というのが怖かったのですが、これで安心して書けそうです。

AtCoder Beginners Contest (ABC) において、A, B問題の速解きテンプレートを作成している人も多く見かけます。しかし、たいていはC++が主流となっています。C++では型の扱いなども問題もあるため、このような場面では型がいつの間にか変換されるような言語を用いたほうが楽であると考えられます。

さて、AtCoderでは多様な言語を選択可能で、”Bash”というものも選択可能です。ABCでもC問題以降のようなものをBashで解くのは面倒かと思いますが、A問題、B問題を速く特にあたってBashを利用することは現実味を帯びているとも考えられます。実際のコンテストの解答一覧で検索しても、実際にBashを利用してA問題やB問題を解いている参加者はちらほらいるようです。また、サーバー管理等でも、自分のやりたいことをBashで書けると便利です。

そのため、ABCのA問題、B問題のような問題を解くために必要となるようなコマンドの使い方をある程度調べながら考えていくことにします。

まず、ABC004 A問題「流行」を見てみます。入力が一つで、入力をN（整数）とした時2*Nを返します。入力が一つのシンプルなパターンでは、入力値を取り出すのに

`cat`

とすることができます。また、bash上での整数の四則演算にはexprが使えますから、

expr `cat` \* 2

とすると解けるはずですね（*はそのままだとワイルドカードとみなされ、カレントディレクトリのファイル名一覧として展開されてしまうためエスケープする必要があることに注意しましょう）。しかし、実際にこれを提出するとRuntime Error (RE)となります。これは、exprでは演算結果が0の時exit statusが1となってしまうため、異常終了とみなされてしまうことにあります。そのため、

expr `cat` \* 2
exit 0

とする必要があります。こうするとACとなります。

入力値が複数ある場合はまた考える必要があります。ABC005 A問題「おいしいたこ焼きの作り方」では、標準入力からスペースで区切られたxとyを読み取り、y/xの値（小数点以下切り捨て）を出力する必要があります。

readコマンドを利用すると、複数の入力を複数の変数に入れることができます。

read a b
expr $b / $a
exit 0

とすると解くことができます。

文字列処理の問題が出てくることもあります。ABC010 A問題「ハンドルネーム」では、受け取った文字列の末尾にppをつけます。
まずはsedを使って

sed -e 's/$/pp/'

とかやることで、正規表現一発で済む問題は解くことができます。

また、ABC005 A問題あたりで出てきたテンプレっぽい何かを使って

read a
echo $a'pp'
exit 0

という風にすることもできます。sedなど、標準入力から読み込むコマンドをつかいたければ

read a
echo $a | sed -e 's/$/pp/'
exit 0

などすることもできます。

ABC 008のA，入力は整数高々3つ・出力は整数1つだろうと決めつけ，予め入出力部分を作っておいた．15秒．

— くりんぺっと (@climpet) May 10, 2014

climpet氏のこの発言に従えば、

read a b c
expr
exit 0

までを事前に用意しておき、問題を読んだら演算結果のみをexprの右に、もし数値演算でなければexprではなくsedなどにすればよいことになります。入力する量はC++で事前にテンプレートを作った場合とそれほど変わらないと思いますが、見た目がシンプルでどこに書くか探しやすいのと、数字ではなく文字列だった場合も対処が楽というメリットがあります。

また、ABC009 B問題「心配性な富豪、ファミリーレストランに行く。」というように、行単位で入力が与えられ、その処理がシンプルに終わる場合、Bashを使うと楽に解けることがあります。

一行目は要らないので（EOFを考えなくても入力できるようになるためのもの）tailコマンドを利用して取り除くことにします。あとは重複を取り除き、大きい方から2番めの数字を取り出すわけですが、それぞれはそういうことをしてくれるコマンドがあるので、

tail -n +2 | sort -n | uniq | tail -n 2 | head -n 1

とすることで楽に求められます。こういうのに慣れると（あとはcutやsedが使えると）目grepだと大変だがそんなに大規模でないログから必要な情報を取り出すのにも役立ちそうです。

また、ABC008 B問題「投票」では、それぞれの行の内容を集計し、最多のものを出す、ということをする必要があります。Bashで集計をするにも、 uniq -c とすると件数を出してくれます。あとはそれを処理すればいいので、

tail -n +2 | sort | uniq -c | sort -n | tail -n 1 | sed -e 's/^ *[0-9]* //g'

とすることができます。

今回はABCのA,B問題ということで基本的なコマンドの色々な挙動を調べつつ覚えていこう、というのが大半になりましたが、Bashでも短くコンパクトに意外と色々なことができます。サーバー上で色々やるために使っていると実際に使用するコードだとPerlなどの既にインストールされたLLのワンライナーを突っ込むこともありますが、ABCのA,B問題のいくつかではよくあるコマンドをパイプすることでBashがコンパクトに解けました。

ここ半年ほどやたらと脆弱性のニュースが多い気がしますが、今度はSSLv3周りでPOODLEとかいう名前だけは可愛い脆弱性の話題、古いものを使っているユーザーをどれほど守るかと、どれほどユーザーの安全を守るかという二つの相反する要素の葛藤を強いられている人も多そうですね。

さて、以前に、ルーターで競技プログラミングという記事を書きました。Advent Calendarに向けて書いた記事で、競技プログラミングを引き合いにルーターのパケット割り振りの機能を用いて計算を行うことができるかという記事で、iptablesを使用してある程度繰り返し処理や記憶を伴う計算をある程度することができそうだ、という感じを出しながら一問解くことができました。しかし、この記事には、iptablesなのでルーターっぽくないという問題点がありました。
この問題を解決するための次のステップとして、自由度はそれほど下がらないと思われつつももう少しルーターっぽい感じの操作体系となるVyOSを用いることを考え、昨年の記事の手法をそのままVyOSに適用可能かについて検討しました。

まずは、VyOSのインストールを行います。VyOSのウェブページから最新版のインストーラ（インストールした時は1.0.5だったので1.0.5で試みましたが、最近1.1.0が出たようです。）のイメージをダウンロードし、起動し、初期設定を行いました。VyOSの解説を目的としたわけではないので、必要ならVyOSのUser Guideを参照してください。

さて、ここで、パケット転送を思い通りに行うために必要なコマンドを実行する必要があります。前回の記事で使用したものでは

• 特定のポートに届いたパケットを特定のホスト・ポートに転送
  • その際、特定のフラグを叩くこともある
  • 特定のフラグが過去60秒に一定回数叩かれていることを前提条件としているものもある

という条件をたくさん設定することにより機能を実現しました。1-65535それぞれのポートがどこに対応するかはPerlで計算した上で予め流し込んでおきました。

今回この手法を設定するにあたり、まずは以下の様なコマンドを用いて転送ができるようでした。

set nat source rule 10 destination port 1
set nat source rule 10 translation address 192.168.150.2
set nat source rule 10 translation port 32769

そして、これの挙動を過去の記憶によって変動させるため、以下の様なコマンドを実行する必要があると思われました。

set nat source rule 10 state new 'hoge'

しかし、これはうまくいきません。

vyos@vyos# set nat source rule 10 state new 'hoge'

  Configuration path: nat source rule 10 [state] is not valid
  Set failed

[edit]

nat sourceのruleに対してstate、というのはうまくいかないようです。firewallについてはうまくいくようですが、これはポートノックや攻撃者をある程度締め出すために使われるようなので、natには不要と判断されるのかもしれません。
これを受け、これと同等のコマンドをウェブ検索や公式ページでの検索で探しましたがみつかりませんでした。

そのため、現状ではVyOSで競技プログラミング、あるいは計算を行うことができていません。今後の課題となると考えられます。

繰り返し処理を行うにあたっては転送によりポートを変えながら何度も転送することは必須と考えられるため、この間にマシン自体の状態を変化させることは、変数を用いた処理を行うのに事実上必要な処理だと思われますが、これができないとなると、VyOSを用いて複雑な計算を行うことは困難であると考えられます。これはルーターで競技プログラミングを行うにあたって重大な障壁であると考えられ、現状では当方では打開策を思いつくに至りません。これについて現状を打破するのにつながる可能性のある情報などがありましたら、是非コメント欄や電子メール、SNSなどでご一報いただければと思います。