AtCoder Beginner Contest 103の解説 - private-yusuke’s diary

A - Task Scheduling Problem

入力: $\displaystyle{A}_{{1}}\ {A}_{{2}}\ {A}_{{3}}\quad{\left({A}_{{i}}\in\mathbb{Z},{1}\le{A}_{{1}},{A}_{{2}},{A}_{{3}}\le{100}\right)}$
出力: i番目のタスク -> j番目のタスクでかかるコスト $\displaystyle{\left|{A}_{{j}}-{A}_{{i}}\right|}$ の最小値

$\displaystyle{\left|{A}_{{j}}-{A}_{{i}}\right|}$ というのは、数直線上に表すと2点間の距離と言い換えることができます。したがって、 $\displaystyle{A}_{{1}},{A}_{{2}},{A}_{{3}}$ の最大値から最小値を引くことでこの問題を解くことができます。

(A => A.reduce!max - A.reduce!min)(readln.split.to!(int[])).writeln;

感想: A問題なのに問題文が難しかった。でも実装はA問題レベルだったなあ。

B - String Rotation

入力:
$S$
$\displaystyle{T}\quad{\left({2}\le{\left|{S}\right|}\le{100},\ {\left|{S}\right|}={\left|{T}\right|},\ {S},{T}\right.}$ は英小文字からなる $)$
出力: 操作(文字列の末端を先頭に持ってくる)を任意の回数繰り返してSをTに一致させられるなら'Yes'、そうでなければ'No'

素直に操作を繰り返せばいいです。（ $\displaystyle{2}\le{\left|{S}\right|}\le{100},{\left|{S}\right|}={\left|{T}\right|}$ なので $\displaystyle{\left|{S}\right|}-{1}$ 回操作を繰り返して一致するタイミングがあればYes)

auto S = readln.chomp, T = readln.chomp;
foreach(i; 0..S.length) {
	string tmp = S[1..$];
	tmp ~= S[0];
	if(S == T) {
		writeln("Yes");
		return;
	}
	S = tmp;
}
writeln("No");

上は素直に操作を繰り返す方法ですが、S同士を連結してSSという文字列(例: S="aba"のとき、SS="abaaba")を作り出し、その中にTが含まれるかを判定することでも解くことができます。

auto S = readln.chomp, T = readln.chomp;
S ~= S;
if(S.canFind(T)) writeln("Yes");
else writeln("No");

感想: SとTをsortしてS=TならYesでええやろ！ｗとか思ってたら全然違いました。ちゃんと考えることが大事。

C - Modulo Summation

入力:
$N$
$\displaystyle{a}_{{1}},\ {a}_{{2}},\ \ldots,\ {a}_{{N}}\quad{\left({a}_{{i}}\in\mathbb{Z},\ {2}\le{N}\le{3000},\ {2}\le{a}_{{i}}\le{10}^{5}\right)}$
出力: $\displaystyle{m}\ge{0}$ に対して、 $f(m) = (m \bmod a_1)+(m \bmod a_2) + \cdots + (m \bmod a_N)$ としたときの $f$ の最大値

入力例1を見てみると、 $f(11) = (11 \bmod 3) + (11 \bmod 4) + (11 \bmod 6) = 10$ が $f$ の最大値となっています。よく見てみると、 $11 \bmod 3,\ 11 \bmod 4,\ 11 \bmod 6$ それぞれの項で最大の値 $2, 3, 5$ をとっていることがわかります。
では、ここでの $11$ はどういう意味を持つのでしょうか。問題では $m>0$ となっていますが、試しに $m=-1$ の場合を考えてみましょう。そうすると…
$f(-1) = (-1 \bmod 3) + (-1 \bmod 4) + (-1 \bmod 6) = (2 \bmod 3) + (3 \bmod 4) + (5 \bmod 6) = 10$ となるのがわかります。ここで、この $-1$ という値を正の整数で表せないか、と考えると、実は $\displaystyle \text{lcm}{{\left({a}_{{1}},\ {a}_{{2}},\ \ldots\ {a}_{{N}}\right)}}-{1}$ で表せるとわかります。実際、 $\text{lcm}{{\left({3},{4},{6}\right)}}-{1}={12}-{1}={11}$ です。というわけで、求めるべき値は最終的に $\displaystyle\sum_{{i}}{\left({a}_{{i}}-{1}\right)}$ とわかります。 $10^5$ 以下で最大の5つの素数 $99929,99961,99971,99989,99991$ をかけ合わせると $9984108835867799588150201$ という莫大な値をとり、これは $\displaystyle{10}^{24.9993}$ ぐらいです。unsigned long long(Dではulong)でも値を保持し続けることはBigIntを用いないと無理です。

auto N = ri;
auto a = readln.split.to!(int[]);
a.map!(b => b-1).sum.writeln;

実は、BigIntを使ってゴリ押しすることもできます。実際にmの値を計算してみる。

readln;
auto a = readln.split.to!(BigInt[]);
BigInt m = a.reduce!"a*b"-1;
ulong tmp;
foreach(i; a) {
	tmp += (m % i).to!ulong;
}
tmp.writeln;

ここで $\displaystyle{m}=\prod_{{i}}{\left({a}_{{i}}\right)}-{1}$ としています。 $\displaystyle{m}= \text{lcm}{{\left({a}_{{1}},{a}_{{2}},\ldots,{a}_{{i}}\right)}}-{1}$ でもどちらでもOKです。
制約上、入力される正整数は3000個まで許容されており、fの最大値をとるmの最小値は14748桁になるようです。
(すべて互いに素だと仮定した場合、上のmの値2つは等しくなりますから、この主張は正しい…はず)

gist.github.com

感想: ゴリ押しでも解けることがわかり、現代のコンピュータの性能はやっぱりヤバイなあと思った。

D - Islands War

入力:
$N\ M$
$a_1\ b_1$
$a_2\ b_2$
$\vdots$
$a_M\ b_M$
制約は: $\displaystyle{2}\le{N}\le{10}^{5},\ {1}\le{M}\le{10}^{5},\ {1}\le{a}_{{i}}<{b}_{{i}}\le{N},\ {i}\ne{j}\Rightarrow{\left({a}_{{i}},{b}_{{i}}\right)}\ne{\left({a}_{{j}},{b}_{{j}}\right)}$
出力: 取り除く必要のある橋の本数の最小値

これは蟻本に乗っている区間スケジューリング問題に似ています。
橋を取り除くにあたり、最も少ない本数で済むようにするには、できるだけ東から切っていけばよいです。

$b_i < b_j$ となるようにソートして、foreachし、もし今までに切った地点より東側で「戦いの西側の国」が存在したら、「その戦いの東側の国の手前」で橋を切り落とす。これでACできます。

alias Task = Tuple!(int, "start", int, "end");

void main() {
	auto ip = readAs!(int[]), N = ip[0], M = ip[1];
	Task[] tasks = new Task[](M);
	foreach(i; 0..M) {
		auto s = readAs!(int[]);
		tasks[i] = Task(s[0], s[1]);
	}
	tasks.sort!"a.end < b.end";

	int d = 0;
	int res;
	foreach(t; tasks) {
		if(d <= t.start) {
			d = t.end;
			res++;
		}
	}
	res.writeln;
}

感想: コンテスト中は「imos法とかUnionFindでいけそう」とか思ってて、解けませんでした。簡単めなD問題なので解きたかった。

A: Submission #2876592 - AtCoder Beginner Contest 103
B: Submission #2878868 - AtCoder Beginner Contest 103
B(連結方式): Submission #2890012 - AtCoder Beginner Contest 103
C: Submission #2877869 - AtCoder Beginner Contest 103
C(BigInt): Submission #2890307 - AtCoder Beginner Contest 103
D: Submission #2890508 - AtCoder Beginner Contest 103