日別アーカイブ: 2016年6月4日

にろきプロコン#1 問題と解説

投稿日時: 投稿者:
返信

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 ≤ i1..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） locationi、問題文中の信号のパラメータxi, yi がスペース区切りで入力されています。

Output

speed

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

制約

1 ≤ N ≤ 100
1 ≤ time ≤ 100,000,000
1 ≤ distance ≤ 100,000,000
1 ≤ speedlimit ≤ 100,000,000
1 ≤ location1..N ≤ distance
1 ≤ y1..N ≤ time
-yi ≤ xi ≤ yi for i in 1..N
locationi-1 ≤ locationi 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;
	}
}