2018-07-22

AtCoder Beginner Contest 103の解説

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

2018-06-17

AtCoder Beginner Contest 100の解説

A - Happy Birthday!

入力: $A\, B\quad (A, B \in \mathbb{Z}; A + B \le 16)$
出力: 可能なら'Yay!', そうでなければ ':('

「隣り合う2切れのケーキを両方取る」というのは、AかBどちらかが8より大きければ発生することなので、

if(A > 8 || B > 8) {
	writeln(":(");
	return;
} else {
	writeln("Yay!");
}

でいいです。
感想: Aなのに問題文が少しむずかしい。

B - Ringo's Favorite Numbers

入力: $D\, N\quad (D = 0,1,2; N \in \mathbb{Z}; 1 \le N \le 100)$
出力: 100でちょうど $D$ 回割り切れるN番目に小さい整数

アアアアアアアアアアアアアアアアアアアーーーーー。
とりあえず、 $N=100$ のときとそうでないときで分けて考えよう。

if(D == 0) {
	if(N == 100) writeln(101);
	else writeln(N);
} else if(D == 1) {
	if(N == 100) writeln(100*101);
	else writeln(100*N);
} else {
	if(N == 100) writeln(100*100*101);
	else writeln(10000*N);
}

感想: ABCをやってきて一番WAしたB問題。制約を読もう。双子が悪魔に見える。

C - *3 or /2

入力:
$N\quad (N \in \mathbb{Z}; 1 \le N \le 10000)$
$a_1\, a_2\, a_3\, \cdots \, a_N\quad (a_i \in \mathbb{Z}; 1 \le a_i \le 1000000000)$
出力: 最大の操作回数

この問題、いかにして $a_i$ を2で割れるのか、というところだけに注目すれば解くことができます。
一回一回の操作で「2で割れる要素のうち1つを決めて除算をし、それ以外は3倍する」ことをすれば、最大の操作回数となるようにできます。3倍しても、2で割れる回数は変わりませんので。

ulong cnt;
foreach(i; a) {
	while(!(i & 1)) {
		i /= 2;
		cnt++;
	}
}
cnt.writeln;

感想: B問題より簡単に感じた。

D - Patisserie ABC

入力:
$N\, M\quad (N, M \in \mathbb{Z}; 1 \le N \le 1000; 0 \le M \le N)$
$x_1\, y_1\, z_1$
$x_2\, y_2\, z_2$
$\vdots\, \vdots$
$x_N\, y_N\, z_N\quad (-10000000000 \le x_i, y_i, z_i \le 10000000000 (1 \le i \le N))$
出力: $\displaystyle\text{max}{\left(\sum_{{i}}{\left|{C}_{{{i}_{{x}}}}\right|}+{\left|{C}_{{{i}_{{y}}}}\right|}+{\left|{C}_{{{i}_{{z}}}}\right|}\right)}$

sortして、 $x \lt y, x \gt y, y \lt z, y \gt z, z \lt x, z \gt x$ というふうに6通りに分けてやればいいんじゃね？！とか思ってたらWAしました。その後いろいろ試すもWAWAWAのWA。方針が間違っている。
ということで、コンテスト中には解けなかったのですが、よい考え方があるので、それを紹介します。

まず、仮に今回の制約で $a_i$ が0以上だったと仮定すると、明らかに、ケーキ毎に $x,y,z$ の総和をとり、その総和が大きい順からM個とってそれらの和をとればよいとわかります。
ケーキ $C_i$ の総和を $\displaystyle{S}_{{i}}={C}_{{{i}_{{x}}}}+{C}_{{{i}_{{y}}}}+{C}_{{{i}_{{z}}}}$ と表し、数列 $\displaystyle{\left\lbrace{S}_{{{C}_{{i}}}}\right\rbrace}$ を降順にソートしたとすると、和は $\displaystyle{\sum_{{{i}={1}}}^{{M}}}{S}_{{i}}$ で表されます。

次に、今回と同じ制約で、 $a_i$ が負の値もとることがあるとしましょう。
ところで、 $|a|$ は $a \ge 0$ のとき $a$ 、そうでないとき $-a$ であることはご存知かと思います。
したがって $\textrm{max}(|a|) = \textrm{max}(a, -a)$ といえます。
よって $\textrm{max}(|a|+|b|) = \textrm{max}(\textrm{max}(a, -a)+\textrm{max}(b, -b)) = \textrm{max}(a+b, a-b, -a+b, -a-b)$ ですね。
だから、 $\textrm{max}(|a|+|b|+|c|) = \textrm{max}(\textrm{max}(a, -a)+\textrm{max}(b, -b)+\textrm{max}(c, -c)) = \textrm{max}(\textrm{max}(a+b, a-b, -a+b, -a-b)+\textrm{max}(c, -c)) = \textrm{max}(a+b+c, a+b-c, a-b+c, a-b-c, -a+b+c, -a+b-c, -a-b+c, -a-b-c)$ です。
要は、絶対値まわりの処理が面倒なので、最初から各ケーキについて八通りのありうる値のとり方を計算しておけば楽なわけです。
この八通りについて、それぞれのパターンでケーキの価値の総和をとっておきます。そうすると、その8つのうちの最大値が求める値になります。

alias Cake = Tuple!(long, "x", long, "y", long, "z", long[], "score");

void main() {
	auto ip = readln.split.to!(long[]), N = ip[0], M = ip[1];
	Cake[] cakes;

	foreach(_; 0..N) {
		auto ip2 = readln.split.to!(long[]), a = ip2[0], b = ip2[1], c = ip2[2];
		long[] score;
		foreach(i; [1,-1]) foreach(j; [1,-1]) foreach(k; [1,-1]) {
			score ~= a*i+b*j+c*k;
		}
		cakes ~= Cake(a, b, c,score);
	}
	ulong res;
	foreach(i; 0..8) {
		cakes.sort!((a, b) => a.score[i] > b.score[i]);
		res = max(res, calc(cakes[0..M]));
	}
	res.writeln;
}

ulong calc(Cake[] cakes) {
	long beat, deli, popu;
	foreach(i; cakes) {
		beat += i.x;
		deli += i.y;
		popu += i.z;
	}
	return abs(beat)+abs(deli)+abs(popu);
}

感想: めっっっちゃ頑張ってsortでゴリ押ししようとしたけどダメだった。精進しなきゃいけないですね。

A: Submission #2674649 - AtCoder Beginner Contest 100
B: Submission #2682146 - AtCoder Beginner Contest 100
C: Submission #2677346 - AtCoder Beginner Contest 100
D: Submission #2689798 - AtCoder Beginner Contest 100

2018-06-11

AtCoder Beginner Contest 099の解説

A - ABD

入力: $N\quad(N \in \mathbb{Z}; 1 \le N \le 1998)$
出力: $N \le 999$ なら "ABC"、 $1000 \le N$ なら "ABD" と出力

auto N = readln.chomp.to!int;
if(N <= 999) {
	"ABC".writeln;
} else {
	"ABD".writeln;
}

感想: はい

B - Stone Monument

入力: $a \, b\quad (a, b \in \mathbb{Z}; 1 \le a < b < 499550(= 1+2+3+\ldots + 999))$
出力: 積もっている雪の高さ $x$

まず、 $1, 3, 6, 10, 15, \ldots, (1+2+3+\ldots+999)$ という数列を用意する。

int[] arr = new int[](999);
arr[0] = 1;
foreach(i; 1..999) arr[i] = arr[i-1] + i+1;

そして、 $b-a$ の値 $d$ を求めて、 $arr_{i+1} - arr_i = d$ ならば、 $arr_i - a$ を出力すればよいです。

int d = b - a;
foreach(i; 0..998) {
	if(arr[i+1] - arr[i] == d) {
		writeln(arr[i] - a);
	}
}

感想: ちょっとだけ考察が難しいかもしれないけど、問題文から「隣り合った柱について、雪に埋もれてない部分の長さがそれぞれ与えられる」ので、これらの差をとれば何番目の柱なのかがわかって、同時に積雪量も求められるとわかります。

C - Strange Bank

入力: $N\quad (N \in \mathbb{Z}; 1 \le N \le 100000)$
出力: この銀行からちょうどN円を引き出すのに必要な操作回数の最小値

僕はDPでときました。漸化式は
$dp[0] = 0$
$dp[i] = min(dp[i-1] + 1, dp[i-6] + 1, dp[i-9] + 1, dp[i-6^2] + 1, \ldots)$
という感じで表せます。具体的に、 $dp[i - x] + 1$ に入る $x$ の値は
${1, 6, 9, 36, 81, 216, 729, 1296, 6561, 7776, 46656, 59049}$ が考えられます。 $(x \le N \le 100000)$
あとはDPするだけです。

int[] dp;
int[] arr = [1, 6, 9, 36, 81, 216, 729, 1296, 6561, 7776, 46656, 59049];
int solve(int i) {
	if(dp[i] >= 0) return dp[i];
	int tmp = int.max;
	foreach(k; arr) {
		if(i < k) break;
		tmp = min(solve(i-k)+1, tmp);
	}
	return dp[i] = tmp;
}
void main() {
	auto N = readln.chomp.to!int;
	dp = new int[](N+1);
	dp[] = -1;
	dp[0] = 0;
	solve(N).writeln;
}

感想: 入力例3で「これ貪欲法じゃ解けねぇ…！ならばDPしかない！！」となり、DPで解きました。

D - Good Grid

入力:
$N \, C\quad (1 \le N \le 500; 3 \le C \le 30)$
$D_{1,1} \, \cdots \, D_{1,C}$
$\vdots$
$D_{C,1} \, \cdots \, D_{C,C}$
$c_{1,1} \, \cdots \, c_{1,N}$
$\vdots$
$c_{N,1} \, \cdots \, c_{N,N}$
出力: すべてのマスに対して感じる違和感の和のとりうる最小値

下の文章の添字は問題文と異なります。 $(i, j) \to (x, y)$
素直に全探索を考えます。そうすると、まずはcの(x, y)成分で $(x+y)\%3$ について、3色を色 $1$ から色 $C$ までで考える必要があるので、それぞれの色を $i, j, k$ とおき、各マスについて条件を満たしているかどうかを調べ、それぞれについて適切な処理を行おうとすると、計算量が $O(C^3 \times N^2)$ となり、これは間に合いません。
そこで、まず前処理として色 $a$ を一つ決め、 $x, y$ についてループを回し、先に違和感をそれぞれ $(x+y)\%3=0, (x+y)\%3=1, (x+y)\%3=2$ の場合について計算しておきます。

auto arr = new int[][](3, C);
foreach(a; 0..C) foreach(x; 0..N) foreach(y; 0..N) {
	arr[(x+y)%3][a] += D[c[x][y]-1][a];
}

次に、実際に3色 $i, j, k$ を三重ループで回し、 $i=j \lor j=k \lor k = i$ の場合に注意して違和感の最小値を取得します。

foreach(i; 0..C) foreach(j; 0..C) foreach(k; 0..C) {
	if(i==j||j==k||k==i) continue;
	res = min(res, arr[0][i]+arr[1][j]+arr[2][k]);
}

そして、 $res$ を出力すればよいです。
感想: コンテスト中は前者の超愚直方式で解こうとしてTLE。終了後にこの方法を知る。まだまだ競プロはわからないことだらけ。

A: Submission #2643843 - AtCoder Beginner Contest 099
B: Submission #2645854 - AtCoder Beginner Contest 099
C: Submission #2649430 - AtCoder Beginner Contest 099
D: Submission #2652709 - AtCoder Beginner Contest 099

2018-06-03

AtCoder Beginner Contest 098の解説

A - Add Sub Mul

入力: $A\;B\quad(A,B \in \mathbb{Z};\, -1000 \le A, B \le 1000)$
出力: $A+B$ , $A-B$ , $A\times B$ の中で最大の値

writeln(max(A+B, A-B, A*B));

感想: はい

B - Cut and Count

入力:
$N\quad (2 \le N \le 100)$
$S\quad (|S| = N)$
出力: Sを一箇所で切断してできた２つの文字列 $X, Y$ のどちらにも含まれている文字の種類数の最大値

「どちらにも含まれている」 -> "setIntersection"

ulong res;
foreach(i; 0..N) {
	auto X = S.dup; // sort()が作用してしまうのでコピーする
	auto a = X[0..i].sort().uniq.array; // 部分列に含まれる文字を取得
	auto b = X[i..$].sort().uniq.array; // (sortで揃えてuniqで隣り合う同要素を一つにする)
	int tmp = setIntersection(a,  b).array.length.to!int; // 文字の種類数
	res = max(res, tmp);
}
writeln(res);

感想: B問題にしては難しい気がする

C - Attention

入力:
$N\quad (2 \le N \le 3\times 10^5)$
$S\quad (|S| = N)$ $S_i$ は 'E' または 'W'
出力: 向く方向を変える人数の最小値

各地点でリーダーを決めて、向く方向を変える人数をforループで数え上げるとTLEします。(サンプルだけ通ってsubtaskは通らない)
ここで、累積和を使います。用意すべき配列は、「i番目含め左から今までのWの個数の配列」です。

auto A = new int[](N);

// i番目含め左から今までのWの個数
A[0] = S[0] == 'W';
foreach(i; 1..N) A[i] = S[i] == 'W' ? A[i-1]+1 : A[i-1];

// i番目含め左から今までのEの個数
// WでないならEがそこにあるため、余事象の考え方が使えます。
auto C = (int n) {
	return n+1 - A[n];
};

foreach(i; 0..N) {
	ulong tmp;
	tmp += C(N-1) - C(i); // リーダーより右でEを向いている人の数
	tmp += i < 1 ? 0 : A[i-1]; // リーダーより左でWを向いている人の数
	res = min(res, tmp);
}
res.writeln;

先に累積和の配列を生成することで、このようなTLEを解消できます。

感想: 累積和全然やってないオタクだったのでコンテスト中に解けず。頭が回らなかった。

D - Xor Sum 2

入力:
$N\quad (1 \le N \le 2 \times 10^5)$
$A_1 \, A_2 \, \ldots \, A_N\quad (A_i \in \mathbb{Z};\, 0 \le A_i \le 2^20)$
出力: $A_l \, {\rm xor} \, A_{l+1} \, {\rm xor} \, \ldots {\rm xor} \, A_r = A_l + A_{l+1} + \ldots + A_r$ を満たす整数 $l, r\, (1 \le l \le r \le N)$ の組の個数

しゃくとり法を使います。

foreach(l; 0..N) {
	// 尺取り法(l: left, r: right)
	// 題意(和とxorが等しい)を満たすなら
	while(r < N && (total + A[r] == (xor_sum ^ A[r]))) {
		total += A[r];
		xor_sum ^= A[r];
		r += 1; // ひとつ右に進める
	}
	res += r - l; // 区間長をたす(一回前までうまくいっていたので)

	// 区間の左端をひとつ右に進めるので、そのぶん(A[i])をなかったことにする
	// 逆演算すればよい。足し算の反対は引き算、xorの反対はxor
	total -= A[l];
	xor_sum ^= A[l];
}
writeln(res);

ある区間 $A = [l, r)$ で条件を満たしているなら、 $\forall a \forall b([a, b))\, (a, b \in A)$ でも条件を満たします。

感想: コンテスト中にたどり着かなかった。しゃくとり法やったことなかった。知らない・理解していないアルゴリズムとか考え方はまだまだたくさんあるので、精進は大事だなあって思った。

A: Submission #2561733 - AtCoder Beginner Contest 098
B: Submission #2564967 - AtCoder Beginner Contest 098
C: Submission #2604714 - AtCoder Beginner Contest 098
D: Submission #2573473 - AtCoder Beginner Contest 098

2018-05-13

AtCoder Beginner Contest 097の解説

お疲れ様でした！

A - Colorful Transceivers

入力: $a\;b\;c\;d\quad(a,b,c,d \in \mathbb{Z};\, 1 \le a, b, c, d \le 100)$

出力: 会話可能なら"Yes", そうでないなら"No"

直接的にaさんとcさんが会話可能…abs(a-c) ≦ d

間接的にaさんとcさんが会話可能…abs(a-b) ≦ d ∧ abs(b-c) ≦ d

この2つのどちらかが成り立つならば会話可能である。

writeln((abs(a - c <= d) || ( abs(a - b) <= d && abs(b - c) <= d) ? "Yes" : "No");

感想: はい

B - Exponential

入力: $X\quad(X \in \mathbb{Z};\, 1 \le X \le 1000)$

出力: X以下の最大のべき乗数( $1^3, 6^4, 2^9$ のような、指数が2以上の数)

まず、1000以下のべき乗数すべてを含むリストを生成する。

処理としては、「まず、与えられた数(2 ≦ a ≦ 1000)を2乗して1000以下ならその数をリストにぶち込み、3乗して1000以下ならその数をリストにぶち込み、4乗して1000以下なら…」というようにしていき、1000より大きな数になったら次の数に移る。これを2から1000までやると欲しいリストの生成が終わる。

int[] arr;
arr ~= 1; // 1をforeachのところに入れると無限ループします＼(^o^)／
foreach(i; 2..1001) {
	auto a = i;
	auto b = a; // aにaをかけていくので、bに最初のaの値を保存する
	auto k = 2; // 指数

	a *= a; // 二乗する
	while(a <= 1000) {
		arr ~= a; // 1000以下のべき乗数であるから、リストに追加する
		k++; // 指数を1増やす
		a = b^^k; // bのk乗をaに代入する
	}
}

[1, 4, 8, 9, 16, 25, 27, 32, 36, 49, 64, 81, 100, 121, 125, 128, 144, 169, 196, 216, 225, 243, 256, 289, 324, 343, 361, 400, 441, 484, 512, 529, 576, 625, 676, 729, 784, 841, 900, 961, 1000] が欲しいリストです。
後は、Xがリストに入っていたなら、その値を出力し、そうでないならXをデクリメントしてもう一度チェックすれば良いです。

auto X = readln.chomp.to!int;
while(true) {
	if(arr.canFind(X)) {
		X.writeln;
		return;
	}
	X--;
}

感想: リストを生成するとき、a^^2を繰り返すだけの処理を最初記述し、それに気づかず1WA。かなしみ。

C - K-th Substring

入力: $s\quad(1 \le |s| \le 5000)$
$K\,\bf(1 \le K \le 5)$

s は異なるsubstringをK個以上持つ

部分点: $|s| \le 50$ なデータセットに正解したら200点/300点がもらえる

$K\,\bf(1 \le K \le 5)$ 。何度でも書きます。 $K\,\bf(1 \le K \le 5)$ 。この問題はかなり容易な思考で解くことができて、単純に考えうるsubstringたちをリストに入れてsortしてuniqueしてK番目を出力すればいい(""を考慮するとK番目)。赤黒木を使っておけば、最後にsort&uniqueする必要すらないんですが、これだけでは部分点しかもらえません。

auto s = readln.chomp, K = readln.chomp.to!int;
auto rbt = new RedBlackTree!string("");
foreach(i; 0..s.length) {
	foreach(j; i..s.length+1) {
		rbt.insert(s[i..j]);
	}
}
rbt.array[K].writeln;

本当に何度でも書きますけど $K\,\bf(1 \le K \le 5)$ 、ですからね。つまり5文字以下のsubstringだけ考えておけばいいので、さっきのコードのinsert部の前に

if(j - i > 5) continue;

を入れるだけでACできてしまいます。
感想: 気づかなかった自分がかなしい。

Cの 1 ≦ K ≦ 5 pic.twitter.com/605ij3SnFp
— public_yusuke (@public_yusuke) 2018年5月12日

D - Equals

入力: $N \, M\, (2 \le N \le 10^5; \, 1 \le M \le 10^5)$
$p_1 \, p_2 \, \ldots \, p_N$ ( $p$ は $1$ から $N$ までの整数を並び替えた順列)
$x_1 \, y_1$
$x_2 \, y_2$
$\vdots$
$x_M \, y_M$
なお、これらの制約は

$1 \le x_j, y_j \le N$
$x_j \neq y_j$
$i \neq j \Rightarrow \{x_i, y_i\} \neq \{x_j, y_j\}$
入力は全て整数

さて、これはUnion Findの典型的な問題らしいです（コンテスト中に解けなかった）。そのため、まずはUnion Findがどのようなものか見ていきましょう。

Union find(素集合データ構造) from AtCoder Inc.

www.slideshare.net

どうやら、 $a \sim b, b \sim c \Rightarrow a \sim c$ であることを取り扱えるデータ構造になっているようです。これを使えば、 $p_i = i$ まで持っていけるかどうかを判断できます。操作は何度でもして良いというところがポイントです。
gist.github.com
これを用意しておきます。
そして、 $x_i - 1$ と $y_i - 1$ をuniteします。これで、どれとどれが交換可能なのかが記録されます。
次に、 $p_i - 1$ と $i$ が交換可能かを判定し、可能ならカウントをインクリメントします。最後にカウントを出力すれば終わりです。

auto uf = new UnionFind!int(N);
foreach(_; 0..M) {
	auto ip2 = readln.split.to!(int[]);
	uf.unite(ip2[0]-1, ip2[1]-1);
}
int res;
foreach(i; 0..N) {
	if(uf.same(p[i]-1, i) res++;
}
res.writeln;

感想: Union Findを知らなかった。すっごく便利でびっくりした。

A: Submission #2494881 - AtCoder Beginner Contest 097
B: Submission #2497541 - AtCoder Beginner Contest 097
C: Submission #2504417 - AtCoder Beginner Contest 097
D: Submission #2505891 - AtCoder Beginner Contest 097

TeXを使ってみたり、はてな記法でSyntax Highlightをさせてみたりしました。すごく便利。便利は正義。

2018-05-13

ことえりのユーザ辞書をGoogle日本語入力用に変換するPythonのスクリプトを作成した

僕「ことえりのユーザ辞書をエクスポートしてGoogle日本語入力にインポートしよう。便利になるに違いない！」

f:id:private_yusuke:20180513154630p:plain

ﾎﾟﾁｯ

f:id:private_yusuke:20180513154716p:plain

は？？？？？キレそう！！！

ということでPython3でスクリプトを組んでみました。

ことえりの辞書をGoogle日本語入力用に変換するPythonスクリプト

使い方はスクリプト内にコメントしてあります。これで今日から快適な辞書ライフを過ごせる。

2018-05-05

AtCoder Beginner Contest 096の解説

お疲れ様でした！

A - Day of Takahashi

入力: a b (a, b ∈ ℤ; 1 ≦ a ≦ 12; 1 ≦ b ≦ 31)

出力: 1月1日からa月b日までの「高橋」の日数

「高橋」…月と日の数が等しい日

まず、a-1月までの「高橋」は確実に含まれるので、

tmp += a-1;

また、bがa以上ならば、a月の「高橋」も含まれるので、

if(b >= a) tmp++;

最後に出力

writeln(tmp);

感想: 1WAした。落ち着いて考えることで、上のような方針が立つ。

B - Maximum Sum

入力: A B C K (A, B, C, K ∈ ℤ; 1 ≦ A, B, C ≦ 50; 1 ≦ K ≦ 10)

出力: K回の操作を終えた後の黒板上の整数の合計としてありうる最大の値

最大の値をとるとき、A, B, Cのうち最も大きい値のみを操作し続けることがわかる。よって

int r = max(A, B, C) * 2 ^^ K;

また、max(A, B, C)をA+B+Cから引いた値、すなわち操作しなかった2つの値についても合計に加えるため

int s = A + B + C - max(A, B, C);

最後に操作後の黒板の整数の合計を出力

writeln(r + s);

感想: 落ち着いて考えることで、上のような方針が立つ。

C - Grid Repainting 2

入力: H W (H, W ∈ ℤ; 1 ≦ H, W ≦ 50)

s(1,1)s(1,2)s(1,3)...s(1,W)

s(2,1)s(2,2)s(2,3)...s(2,W)

…

s(H,1)s(H,2)s(H,3)...s(H,W)

なお ∀i∀j(s(i,j) = '#' ∨ s(i,j) = '.') (1 ≦ i ≦ H, 1 ≦ j ≦ W)

出力: 目標達成が可能なら"Yes", そうでないなら"No"

まずsを2次元配列として読み取る。

'#'に着目する。('.'は初期状態としてすべてのマスに配置されているので、着目しない。)

'#'の近傍4マスに'#'が存在しないならば、すなわち目標を達成することは不可能であることがわかる。よって、'#'を探し、もし存在したら、そこの近傍4マスを探索し、その4マスのどこにも'#'が存在しないならば"No"を即座に出力して終了すればよい。そして、もしすべてのマスが条件を満たしているならば、"Yes"を出力して終了すればよい。解答例は下にまとめてある。

感想: こういう「近傍nマス」みたいなことをするプログラムを書くのに慣れてきた。マインスイーパーとか実装するときよく使う。これにDFS組み合わせたりすると面白くなる。

D - Five, Five Everywhere

入力: N (N ∈ ℤ; 5 ≦ N ≦ 55)

出力: 長さNの数列a_1, a_2, ..., a_Nを出力する。

ただし…

a_i(1 ≦ i ≦ N) は 55,555 以下の素数
i ≠ j ⇔ a_i ≠ a_j
数列aからどのような異なる5個の整数の組み合わせを選んでも、合計が合成数になる

条件を満たす数列が複数個あるなら、どれを出力してもよい。

まず2から1381までの素数を含んだリストを用意する。エラトステネスの篩とかで。

ここで、10n + 1(a ∈ ℤ+)な形をしている素数に着目する。それぞれ異なる5個の素数を、10a+1, 10b+1, 10c+1, 10d+1, 10e+1とおくと、合計は

10(a+b+c+d+e)+5 = 5(2a+2b+2c+2d+2e+1)

となる。ここで、2a+2b+2c+2d+2e+1が2以上であることは明らかなので、10n+1な形をしている素数を55個集めておけば、この問題は解くことが可能である。そのような素数は

11 31 41 61 71 101 131 151 181 ...

と続く。

つまり、一度素数列を生成した後、文字列に変換して一桁目を取得してそれが'1'なら列に入れる、といったfilterの操作をしておいて、そのリストの0個目からN-1個目の値を出力するなどすればよい。

なお、10n+1だけでなく、10n+3, 10n+7の形をした素数列を出力することでも解ける。証明は省略。10n+3の形が一番コストが低いかも？(1303まで用意すれば十分だから)

追記: 想定解の、「5で割って1あまる素数の列」は上の10n+1の形の素数列と全く同じ列を生成する。5(2k+1)+1 = 10k+6 = 2(5k+3)で、商が奇数のときは素数ではないので、結局同じものになる。10n+3, 10n+7の形をした素数列についてもAtCoderで提出をしてACを確認した。

感想: 数学な問題は普段数ⅡBの問題を解くときとかにも使える考え方が適用できたりして面白い。最初「素数列生成してそのまま出せばいいだろ〜ｗ」みたいな甘い考えをしていたら普通にWAされた。A問題と合わせて10分のペナルティがprivate_yusukeを襲ったのであった。

A: https://beta.atcoder.jp/contests/abc096/submissions/2460648

B: https://beta.atcoder.jp/contests/abc096/submissions/2459724

C: https://beta.atcoder.jp/contests/abc096/submissions/2461606

D: https://beta.atcoder.jp/contests/abc096/submissions/2463242