AtCoder Beginner Contest 145の解説[A to D]

A - Circle

入力: $r$
出力: $r^2$
制約: $1 \le r \le 100$

半径 $1$ の円の面積: $1^2 \pi = \pi$
半径 $r$ の円の面積: $r^2 \pi$
ゆえに、求めるものは $\frac{r^2\pi}{\pi} = r^2$ である。

writeln(r*r);

感想: タイピングゲーム FA速すぎ

B - Echo

入力:
$N$
$S$
出力: 条件を満たせば'Yes', そうでなければ'No'
制約:

$1 \le N \le 100$
$S$ は英小文字から成る
$|S| = N$

問題文にある通り、「Sが、ある文字列を二度繰り返したものであるか否か」を判定します。Sの前半部分と後半部分が一致するか確かめればよいです。

if(S[0..N/2] == S[N/2..$]) writeln("Yes");
else writeln("No");

感想: やるだけ

C - Average Length

入力:
$N$
$x_1\ y_1$
$\vdots$
$x_N\ y_N$
出力: 経路の長さの平均値
制約:

$2 \le N \le 8$
$-1000 \le x_i, y_i \le 1000$
$i \ne j$ ならば $(x_i, y_i) \ne (x_j, y_j)$
$N, x_i, y_i \in \mathbb{Z}$

たとえば3個の町がある場合(N = 3のとき)、考えうる訪れ方は

1 -> 2 -> 3
1 -> 3 -> 2
2 -> 1 -> 3
2 -> 3 -> 1
3 -> 1 -> 2
3 -> 2 -> 1

の $3! = 6$ 通りあります。問題文にある通り、このような訪れ方は $N!$ 通りあります。

上記のような順列を列挙したい…… そんなあなたには……ｼﾞｬｼﾞｬｰﾝ ☆nextPermutation☆ (C++ではstd::next_permutation)

$ rdmd --eval="auto a = [1,2,3]; do{writeln(a);}while(nextPermutation(a));"
[1, 2, 3]
[1, 3, 2]
[2, 1, 3]
[2, 3, 1]
[3, 1, 2]
[3, 2, 1]

こんな風にいい感じにやってくれます！これを利用しましょう。

void main() {
	auto N = readln.chomp.to!int;
	double res = 0;
	alias Pair = Tuple!(int, "ind", int, "x", int, "y");
	Pair[] pairs;
	foreach(i; 0..N) {
		auto ip = readln.split.to!(int[]), x = ip[0], y = ip[1];
		pairs ~= Pair(i, x, y);
	}
	do {
		double tmp;
		foreach(i; 0..N-1) {
			auto p1 = pairs[i], p2 = pairs[i+1];
			tmp += dis(p1.x, p2.x, p1.y, p2.y);
		}
		res += tmp;
	} while(nextPermutation(pairs));
	writefln("%.8f", res / fact(N));
}

int fact(int n) {
	if(n == 0) return 1;
	else return fact(n-1) * n;
}
double dis(double x1, double x2, double y1, double y2) {
	return sqrt(pow(x1-x2, 2) + pow(y1-y2, 2));
}

$(x_1, y_1), (x_2, y_2)$ の距離を求める関数disを用意しました。
これは $\sqrt{(x_1 - x_2)^2 + (y_1 - y_2)^2}$ を計算します。
こうやって全通りの順列を試して、最後に $N!$ で割ればよいです。

$2 \le N \le 8$ という制約のため試すべき場合は高々 $8! = 40320$ 通りだけしかありません。したがって、この問題を $O(N!)$ の解法を用いて解くことができました。

感想: 基本に戻って全部試すことが大事な問題でした。私はデバッグ出力を消し忘れて1WAしました。かなしい。

D - Knight

入力: $X\ Y$
出力: $(0, 0)$ -> $(X, Y)$ までの行き方の場合の数を10億7で割った余り
制約:

$1 \le X, Y \le 10^6$
$X, Y \in \mathbb{Z}$

dp[x][y]: $(x, y)$ までの行き方の場合の数(mod 10億7)として、
dp[x][y] = dp[x-1][y-2] + dp[x-2][y-1]
dp[0][0] = 1
(添字が範囲外なら配列の値は0として考える)
とすればいい感じに解けそうですが、 $O(XY)$ は最悪の場合 $10^{12}$ になるので間に合いません。

しかし、この解法を組めば小さな $X, Y$ の場合の問題を解くことができて、眺めるとパスカルの三角形が関係していることがわかります。

f:id:private_yusuke:20191117012552p:plain

実際、 $(i, j)$ -> $(i+1, j)$ or $(i, j+1)$ という遷移だったらまさにその通りになります。

f:id:private_yusuke:20191117012536p:plain

求めるものは、 $k := \frac{X + Y}{3}$ が整数になるとき $_kC_{X-k}$ 、そうでないときは $0$ となります。

nCr mod p の高速な求め方は、下記ブログを参考にしてください(けんちょんさんのブログは参考になることばかりなので、読者になりましょう)。↓↓↓

drken1215.hatenablog.com

void main() {
	auto ip = readln.split.to!(int[]), X = ip[0], Y = ip[1];
	auto k = (X + Y) / 3;
	if((X + Y) % 3 != 0) {
		writeln(0);
		return;
	}
	new COM(max(X, Y) + 1, 1000000007).nCr(k, X-k).writeln;
}

class COM {
	long[] fact, finv, inv;
	private ulong MAX;
	private ulong MOD;

	this(ulong MAX, ulong MOD) {
		this.MAX = MAX;
		this.MOD = MOD;
		fact = new long[](MAX);
		finv = new long[](MAX);
		inv = new long[](MAX);

		// initialize the arrays
		fact[0] = fact[1] = 1;
		finv[0] = finv[1] = 1;
		inv[1] = 1;
		foreach(i; 2..MAX) {
			fact[i] = fact[i - 1] * i % MOD;
			inv[i] = MOD - inv[MOD%i] * (MOD / i) % MOD;
			finv[i] = finv[i - 1] * inv[i] % MOD;
		}
	}

	ulong nCr(long n, long k) {
		if(n < k) return 0;
		if(n < 0 || k < 0) return 0;
		assert(n < MAX && k < MAX);
		return fact[n] * (finv[k] * finv[n - k] % MOD) % MOD;
	}
	ulong factorial(long n) {
		return fact[n];
	}
}

感想: ABCでも逆元を用いた高速なnCrを求めるアルゴリズムが要求されるようになったんですね。私はコンテスト終了20分前にパスカルの三角形に気づき、そこからnCrの高速な求め方を調べて実装しました。レートは落ちました。──完──

A: Submission #8461953 - AtCoder Beginner Contest 145
B: Submission #8464057 - AtCoder Beginner Contest 145
C: Submission #8470993 - AtCoder Beginner Contest 145
D: Submission #8486307 - AtCoder Beginner Contest 145