2018-12-09

第18回日本情報オリンピック予選の感想

概要

お疲れ様でした！ABC3完 + D15点 + E10点 + F6点でした。合計331点。

本番の流れ

まずは22分でCまで解きました。Bで焦って15分使ってしまった。
そこから愚直にDを書いて、7点を取りました。とりあえず部分点を取っていくことにして、Eで10点まで取りました。
それから2時間半ほどDにつぎこんで、「二分探索か？」「キュー2つ用意してみよう」「DPではないだろうな」とかやって結局15点まで取り、終了直前にFで6点取りました。

A

愚直にシミュレーションをする。

B

実装が少し面倒でした。愚直にシミュレーションをしましょう。

C

マルとバツの列を左から見ていきます。最後に見たスタンプの形を覚えておきましょう。
マルバツスタンプを使って押したところから十分に離れているかどうかを判定して、そうであってかつ最後に見たスタンプと違う形をしているならば、使った回数をインクリメントします。

D

部分点(15点)でした。
与えられた配列をソートして、各要素から0を引き、そこから0より小さい要素を除外した配列を作ります。
それをforeachして、それぞれを海面の高さとし、島の数の最大値を出しました。(TLE)

E

部分点(10点)でした。
$2^N$ 通りの飾りつけを考えられるので、これを全探索しました。(TLE)

F

部分点(6点)でした。
nextPermutationしました。これだと、同じ国の人が複数いるとき、彼らを一人一人区別することができません。
そのため、条件を満たす並びがあったときは、「与えられた配列のそれぞれについて階乗を計算し、それらをかけあわせた値」を場合の数として足しました。(TLE)

感想

AtCoderのレート相当の点数だったと思います。予選落ちでしょ。
Dの解法が思いつかなかったのが悔しいですが、「部分点を取るぞ！」という気持ちを忘れずにEやFも考えることができました。

docs.google.com

この表を見てると「オア〜〜〜〜〜」という気持ちになりますが(TLの人つよすぎ)、逆にまだまだ伸びしろがあると考えるのがよさそうです(ポジティブになりたいね)。
ボーダーがどうなるのか非常に気になります。TLの人々は本選でも頑張ってくださいね！！

2018-11-25

CODE THANKS FESTIVAL 2018の解説

A - Two Problems

入力:
$T\ A\ B\ C\ D$
制約:
$1 \le T,A,B,C,D \le 10^9$
$T,A,B,C,D \in \mathbb{Z}$

出力: 高橋君の取りうる最大の得点

$A$ 分かけて $B$ 点
$C$ 分かけて $D$ 点とれます。
それで、 $T$ 分の時間があります。
$B \le D$ になっているので、まずは $C$ 分かけて $D$ 点取れないかを調べて、次に $A$ 分かけて $B$ 点とれないかどうかを判定すればよいです。

ulong res;
if(T - C >= 0) {
	T -= C;
	res += D;
}
if(T - A >= 0) {
	res += B;
}
res.writeln;

感想: 普通のA問題。

B - Colored Balls

入力:
$X\ Y$
出力: 箱を空にできるなら'Yes'、そうでないなら'No'
制約:
$0 \le X, Y \le 10^9$
$X+Y > 0$
$X, Y \in \mathbb{Z}$

$X$ と $Y$ を比較して、小さい方は3を引き、大きい方からは1を引く操作を繰り返します。 $X = 0 \land Y = 0$ になったら、'Yes'を出力します。
操作の途中で、 $X < 0 \lor Y < 0$ になってしまったら、'No'を出力すればよいです。

bool flag = true;
while(flag) {
	if(X == 0 && Y == 0) {
		writeln("Yes");
		return;
	}
	if(X > Y) {
		if(X - 3 >= 0 && Y - 1 >= 0) {
			X -= 3;
			Y--;
		} else flag = false;
	} else {
		if(Y - 3 >= 0 && X - 1 >= 0) {
			Y -= 3;
			X--;
		} else flag = false;
	}
}
writeln("No");

感想: 3WA。変に難しいことをしないで、単純に処理を書いたらACできた。

C - Pair Distance

入力:
$N$
$x_1\ x_2\ \cdots\ x_{N-1}\ x_N$
出力: この街の交流コスト

制約:
$2 \le N \le 10^5$
$0 \le |x_i| \le 10^8$
$x_i$ は全て異なる
$N, x_1, x_2, \cdots, x_N \in \mathbb{Z}$

単純に必要なコストを計算すると、 $\displaystyle_{N}{C}_{{2}}=\frac{1}{{2}}\cdot{\left({N}-{1}\right)}\cdot{N}$ となり、最悪の場合に $\displaystyle{\left({10}^{5}\right)}^{2}={10}^{10}$ となってしまい間に合わなくなってしまうかもしれません。
そこで、少し工夫を加えてみます。

まず、与えられたリスト $\displaystyle{\left\lbrace{x}_{{n}}\right\rbrace}$ をソートします。そうすると、 $\displaystyle{\left|{x}-{y}\right|}$ で計算されていたコストを、 $i < j$ として $j-i$ で計算できるようになります。
それと、 $x_i$ は負の値もとりますが、後々の計算で不都合が生じるので、リスト $\displaystyle{\left\lbrace{x}_{{n}}\right\rbrace}$ の最小値をリスト $\displaystyle{\left\lbrace{x}_{{n}}\right\rbrace}$ のそれぞれの要素から引いておきます(そうすると最小値が0に揃い、計算するときに負の値を考慮しなくてよくなります)。
また、愚直に計算をするとTLEするので、累積和を使います。

$\displaystyle{S}_{{n}}={x}_{{1}}+{x}_{{2}}+\ldots+{x}_{{n}}$ とすると、交流コストは $N=3$ のとき
$\displaystyle{\left({x}_{{3}}-{x}_{{1}}\right)}+{\left({x}_{{3}}-{x}_{{2}}\right)}+{\left({x}_{{2}}-{x}_{{1}}\right)}={\left({2}{x}_{{3}}-{S}_{{2}}\right)}+{\left({x}_{{2}}-{S}_{{1}}\right)}$ のようになります。
一般化すると、
$\displaystyle{\left\lbrace{\left({n}-{1}\right)}{x}_{{n}}-{S}_{{{n}-{1}}}\right\rbrace}+{\left\lbrace{\left({n}-{2}\right)}{x}_{{{n}-{1}}}-{S}_{{{n}-{2}}}\right\rbrace}+\ldots+{\left({1}\cdot{x}_{{2}}-{S}_{{1}}\right)}$
のようになります。
これによって、 $\displaystyle\text{O}{\left({n}\right)}$ で計算することができました。

auto N = readln.chomp.to!int;
auto x = readln.split.to!(long[]).sort().array;
auto m = x.reduce!min;
x = x.map!(i => i - m).array;
long[] arr = new long[](N);
arr[0] = x[0];
foreach(i; 1..N) {
	arr[i] = arr[i-1] + x[i];
}
ulong res;
foreach_reverse(i; 1..N) {
	res += i*x[i] - arr[i-1];
}
res.writeln;

感想: ちょっと難しい問題だった。

D - Concatenation

入力: $S$
出力: 連結して $S$ になるような題意の文字列の個数の最小値
制約:
$1 \le |S| \le 10^5$
$S$ は英小文字からなる

「連結」とは、今ある文字列の末尾に新たに文字列をつなげることです。
与えられた文字列 $S$ を先頭から一つずつ見ていきます。
元となるそれぞれの文字列には、先頭と同じ文字が複数含まれていない、とのことであるから、これと「先頭の文字がその文字列においてアルファベット順で最小」より「先頭の文字と同じまたはアルファベット順でそれより小さい文字」があった場合には新たな文字列を繋げる必要があります。

dchar now = S[0];
ulong cnt = 1;
foreach(i; S[1..$]) {
	if(now >= i) {
		cnt++;
		now = i;
	}
}
cnt.writeln;

感想: これ絶対Cより簡単だった。200点で出てもおかしくなさそう。

E 〜H

感想: 全然わからん。

A: Submission #3664315 - CODE THANKS FESTIVAL 2018(Parallel)
B: Submission #3664516 - CODE THANKS FESTIVAL 2018(Parallel)
C: Submission #3666265 - CODE THANKS FESTIVAL 2018(Parallel)
D: Submission #3664994 - CODE THANKS FESTIVAL 2018(Parallel)

2018-10-07

AtCoder Beginner Contest 112の解説

A - Programming Education

入力:
$1$
または
$2$
$A$
$B$
制約:
$N$ は1または2
$\displaystyle{A}\in\mathbb{Z};{1}\le{A}\le{9}$
$\displaystyle{B}\in\mathbb{Z};{1}\le{B}\le{9}$

出力: $N = 1$ のとき、'Hello World'と出力し、 $N = 2$ のとき、 $A + B$ を出力する。

今回は珍しいことに処理の分岐をする必要がありました。

N = readln.chomp.to!int;
if(N == 1) {
	writeln("Hello World");
} else {
	auto A = readln.chomp.to!int, B = readln.chomp.to!int;
	writeln(A + B);
}

感想: やるだけです。問題文がヤバいなあって感じ。

B - Time Limit Exceeded

入力:
$N\ T$
$c_1\ t_1$
$c_2\ t_2$
$\vdots$
$c_N\ t_N$
出力: コストが最小となる経路のコストを出力
制約:
$\displaystyle{N},{T},{c}_{{i}},{t}_{{i}}\in\mathbb{Z}$
$\displaystyle{1}\le{N}\le{100}$
$\displaystyle{1}\le{T}\le{1000}$
$\displaystyle{1}\le{c}_{{i}}\le{1000}$
$\displaystyle{1}\le{t}_{{i}}\le{1000}$
$\displaystyle{i}\ne{j}\Rightarrow{\left({c}_{{i}},{t}_{{i}}\right)}\ne{\left({c}_{{j}},{t}_{{j}}\right)}$

まず、 $T$ 以内に帰宅できない経路については弾きます。この条件を満たすコストの中での最小値を出力すればよいです。

int[] times;
foreach(i; 0..N) {
	/* 入力を読み込む。 */
	if(t <= T) times ~= c;
}
if(times.length != 0) writeln(times.reduce!min);
else writeln("TLE");

感想: 'TLE'のときのケースについて処理するのを忘れてしまうと
'WA'するので気をつけましょう。

C - Pyramid

入力:
$\displaystyle{N}$
$\displaystyle{x}_{{1}}\ {y}_{{1}}\ {h}_{{1}}$
$\displaystyle{x}_{{2}}\ {y}_{{2}}\ {h}_{{2}}$
$\displaystyle{x}_{{3}}\ {y}_{{3}}\ {h}_{{3}}$
$\displaystyle\vdots$
$\displaystyle{x}_{{N}}\ {y}_{{N}}\ {h}_{{N}}$

出力: $\displaystyle{C}_{{X}}\ {C}_{{Y}}\ {H}$

制約:
$\displaystyle{N},{x}_{{i}},{y}_{{i}},{h}_{{i}}\in\mathbb{Z}$
$\displaystyle{1}\le{N}\le{100}$
$\displaystyle{0}\le{x}_{{i}},{y}_{{i}}\le{100}$
$\displaystyle{0}\le{h}_{{i}}\le{10}^{9}$
$\displaystyle{i}\ne{j}\Rightarrow{\left({x}_{{i}},{y}_{{i}}\right)}\ne{\left({x}_{{j}},{y}_{{j}}\right)}$
$\displaystyle{C}_{{X}}\ {C}_{{Y}}\ {H}$ はちょうど1つに特定される

このような制約や条件が複雑な問題は、全探索をすることを考えます。
具体的には、今回は $\displaystyle{C}_{{X}}\ {C}_{{Y}}\ {H}$ の3つの値について全探索すればよいです。

foreach(posY; 0..101)
{
	foreach(posX; 0..101)
	{
		foreach(H; h.reduce!min..h.reduce!min+201)
		{
			bool flag = true;
			foreach(i; 0..N)
			{
				auto dist = max(0, H-abs(posX-x[i])-abs(posY-y[i]));
				if(dist != h[i])
				{
					flag = false;
					break;
				}
			}
			if(flag)
			{
				writefln("%d %d %d", posX, posY, H);
				return;
			}
		}
	}
}

感想: コンテスト中に解けなかった。「基本は全探索」この言葉を忘れてはいけない。あと、実行時間の制約も見ておくべきだと思った。

D - Partition

入力: $N\ M$
出力: $\displaystyle \gcd{{\left({a}\right)}}$ の最大値
制約:
$\displaystyle{N},{M}\in\mathbb{Z}$
$\displaystyle{1}\le{N}\le{10}^{5}$
$\displaystyle{N}\le{M}\le{10}^{9}$

サンプルにない例を見てみましょう。
$\displaystyle{N}={2},{M}={195}$ としてみます。この場合、出力は65になります。

195を素因数分解してみると、 $\displaystyle{195}={3}\cdot{5}\cdot{13}$ となります。
ここで注目したいのは、 $\displaystyle{5}\cdot{13}={65}$ が出力になっていることです。
では $3$ はどこにいったのか、と考えてみると、実は $\displaystyle{\left({a}_{{1}},{a}_{{2}}\right)}={\left({65},{130}\right)},{\left({130},{65}\right)}$ の場合が考えられることから、それぞれ $65$ を1つか2つずつ取っていることがわかります。
よって、「N以上でMを割りきれる最小の数」を探して、その値でMを割った値を出力すればいい、という方針が立ちます。なお、この値を $k$ とすると、探索すべきkの範囲は $\displaystyle{N}\le{k}\le\frac{M}{{2}}$ で十分です。

ただし、このやり方だと、テストケースにはないものの、一番計算に時間がかかるような「Nが2でMが $10^9$ 以下の素数」などのパターンだと多分間に合わなくなってしまいます。
ジャッジ側が少しだけ情けを与えてくれたためにACすることができました。

int k = N;
while(k <= M / 2) {
	auto r = M % k;
	if(r == 0) {
		writeln(M / k);
		return;
	}
	k++;
}
writeln(1);

感想: 割と単純明快なコードでACすることができました。
C問題より簡単に感じましたが、chokudaiさん曰く「それはAtCoderで遊んでいる層が数学に強い傾向にあるためであって、一般的にはC < Dという難易度になっているのは間違いないはず」とのことでした。
確かに全探索することを思いつけば簡単だったのかも…?

A: Submission #3341345 - AtCoder Beginner Contest 112
B: Submission #3342324 - AtCoder Beginner Contest 112
C: Submission #3357731 - AtCoder Beginner Contest 112
D: Submission #3348620 - AtCoder Beginner Contest 112

2018-09-09

AtCoder Beginner Contest 109の解説

A - ABC333

入力: $\displaystyle{A}\ {B}\quad{\left({1}\le{A},{B}\le{3},{\left\lbrace{A},{B}\right\rbrace}\subset\mathbb{Z}\right)}$
出力: $\displaystyle{A}\times{B}\times{C}$ が奇数となるような $1$ 以上 $3$ 以下の整数 $C$ が存在するならば'Yes'を、そうでなければ'No'を出力

まず、Cの値を掛けるとき、Cが偶数だとしたら、 $\displaystyle{A}\times{B}\times{C}$ は偶数になってしまいますから、仮に出力が'Yes'となるならば、掛けるCの値は $1$ か $3$ です。
後はAとBの値に着目します。 $A$ と $B$ の値が与えられたとき、少なくとも1つの数が偶数ならば、この条件を満たすことはできません。よって、最終的には $A$ と $B$ の偶奇を判定すればよいとわかります。

if((A * B) % 2 == 0) writeln("No");
else writeln("Yes");

感想: ごく普通のA問題でした。

B - Shiritori

入力:
$N$
$W_1$
$W_2$
$\vdots$
$W_N$
制約は: $\displaystyle{\left({2}\le{N}\le{100}\right)}$ 、 $W_i$ は英小文字からなる長さ $1$ 以上 $10$ 以下の文字列
出力: 高橋くんのどの発言もしりとりのルールを守っていたなら'Yes'を、そうでなければ'No'を出力

しりとりで大事なルールは2つあります。

まだ発言されていない単語のみ使える
発言した単語の先頭の文字は直前の単語の末尾と一致する

この2つのどちらかが成り立っていなければ、しりとりは成立しません。

では、「まだ発言されていない単語のみ使える」をまず実装してみましょう。
今回の制約では $\displaystyle{2}\le{N}\le{100}$ ということもあって、わざわざ赤黒木を使う必要はありません。普通に配列を用意して、そこに発言の内容を格納しておき、発言の正当性を判定するときにはfor文で過去の発言とダブっていないか判定すればよいです。

string[] m;

// 判定するときのコード(SはW_i)
foreach(j; m) {
	if(S == j) {
		writeln("No");
		return;
	}
}

次に、「発言した単語の先頭の文字は直前の単語の末尾と一致する」を実装しましょう。
これは、毎回の入力ごとにその発言の末尾の文字を変数にもっておけばできます。

dchar last;

// 判定するときのコード(SはW_i)
if(last == S[0]) {
	last = S.back;
} else {
	writeln("No");
	return;
}

また、 $W_1$ のときは自由な発言ができるので、これも考慮して実装します。

auto N = readln.chomp.to!int;
dchar last;
string[] m;
foreach(i; 0..N) {
	auto S = readln.chomp;
	if(i==0) {
		m ~= S;
		last = S.back;
		continue;
	}
	if(last == S[0]) {
		last = S.back;
	} else {
		writeln("No");
		return;
	}
	foreach(j; m) {
		if(S == j) {
			writeln("No");
			return;
		}
	}
	m ~= S;
}
writeln("Yes");

感想: 自分語りになりますが、実はコンテスト前の金曜日に友達としりとりをしながら下校していて、その後電車に乗っているときにしりとりの妥当性を判定するプログラム(まさにこれっぽい!)を考えていたので、これが出題されたときには驚きました。

C - Skip

入力:
$\displaystyle{N}\ {X}$
$\displaystyle{x}_{{1}}\ {x}_{{2}}\ \ldots{x}_{{N}}$
出力: 全ての都市を $1$ 度以上訪れることのできる $D$ の最大値

可能な移動は、

座標 $y$ から座標 $y + D$ に移動する
座標 $y$ から座標 $y - D$ に移動する

とあり、しかも移動は何度でもできるので、

座標 $y$ から座標 $y + nD$ に移動する $\displaystyle{\left({n}\in\mathbb{Z}\right)}$

という操作ができるといえます。

また、座標 $X$ から移動を開始する、とありますが、利便性のためにすべての座標に関して $\displaystyle{\left|{x}_{{i}}-{X}\right|}$ で上書きします。
入力例で試してみましょう。
入力例1で上書きをしてみると、配列は $\displaystyle{\left[{2},{4},{8}\right]}$ となります。
入力例2では、 $\displaystyle{\left[{48},{24},{24}\right]}$ となり、
入力例3では、 $\displaystyle{\left[{999999999}\right]}$ となります。
ここで着目すべきことは、それぞれの出力が、これら配列の要素の最大公約数になっている、ということです。
実際、上書きした配列を元に考えてみると、正整数 $D$ の最大値を求める上で「可能なだけ一気に移動する」「全ての都市を1度以上訪れる」を成り立たせるためには、各要素の最大公約数を求めればいいことがわかります。
よって、コードは次のようになります。

auto ip = readln.split.to!(int[]), N = ip[0], X = ip[1];
auto x = readln.split.to!(int[]).map!(i => i - X).map!(i => i.abs);
auto c = x[0];
foreach(i; x[1..$]) {
	c = gcd(i, c);
}
c.writeln;

感想: 最近はすぐに「これはgcdを使いそうな問題だな」とかそういう気づきをすぐに得られるようになってきたので嬉しい。

D - Make Them Even

入力:
$\displaystyle{H}\ {W}$
$\displaystyle{a}_{{{11}}}\ {a}_{{{12}}}\ \ldots{a}_{{{1}{W}}}$
$\displaystyle{a}_{{{21}}}\ {a}_{{{22}}}\ \ldots{a}_{{{2}{W}}}$
$\displaystyle\vdots$
$\displaystyle{a}_{{{H}{1}}}\ {a}_{{{H}{2}}}\ \ldots{a}_{{{H}{W}}}$
制約は: 入力はすべて整数である、 $\displaystyle{\left({1}\le{H},{W}\le{500},{0}\le{a}_{{{i}{j}}}\le{9}\right)}$
出力: 偶数枚のコインが置かれたマスの数が最大となるような操作の列を次の形式で出力する
$N$
$\displaystyle{y}_{{1}}\ {x}_{{1}}\ {y}'_{{1}}\ {x}'_{{1}}$
$\displaystyle{y}_{{2}}\ {x}_{{2}}\ {y}'_{{2}}\ {x}'_{{2}}$
$\displaystyle\vdots$
$\displaystyle{y}_{{N}}\ {x}_{{N}}\ {y}'_{{N}}\ {x}'_{{N}}$
1行目の $N$ は操作の回数を表す $0$ 以上 $\displaystyle{H}\times{W}$ 以下の整数である。
$\displaystyle{i}+{1}\ {\left({1}\le{i}\le{N}\right)}$ 行目には $i$ 回目の操作を表す整数 $\displaystyle{y}_{{i}},{x}_{{i}},{y}'_{{i}},{x}'_{{i}}\ {\left({1}\le{y}_{{i}},{y}'_{{i}}\le{H},{1}\le{x}_{{i}},{x}'_{{i}}\le{W}\right)}$ を出力する。
これは、マス $\displaystyle{\left({y}_{{i}},{x}_{{i}}\right)}$ にあるコインのうち $1$ 枚を上下左右に隣接するマス $\displaystyle{\left({y}'_{{i}},{x}'_{{i}}\right)}$ に移動させる操作を表す。

まず、この操作はどのような順番でやっても結果には影響しません。入力例1で左上からfor文を回すように見ていき、もしもそのマスのコインの数が奇数ならば、上下左右に隣接したマスを見て、そのマスにコインを渡す、という操作をすればいいです。

また、出力のために、移動の情報は保持しておく必要があります。今回はContというTupleを用意しました。

alias Cont = Tuple!(int, "sx", int, "sy", int, "gx", int, "gy");
auto ip = readln.split.to!(int[]), H = ip[0], W = ip[1];
auto a = readMatrix!int(H, W); // オレオレライブラリにあります。下の提出URL参照
ulong cnt;
Cont[] conts;

auto dx = [1,0,-1,0], dy = [0,1,0,-1];
foreach(i; 0..H) {
	foreach(j; 0..W) {
		foreach(k; 0..4) {
			auto ry = i + dy[k], rx = j + dx[k];
			if(0 <= ry && ry < H && 0 <= rx && rx < W &&
				a[i][j]%2 != 0) {
				a[ry][rx]++;
				a[i][j]--;
				cnt++;
				conts ~= Cont(i+1, j+1, ry+1, rx+1);
				continue;
			}
		}
	}
}
cnt.writeln;
conts.each!(i => writefln("%d %d %d %d", i.sx, i.sy, i.gx, i.gy));

感想: このコードはどの出力例とも異なった出力をしますが、それでもACします(それはそう)。最近の激ムズD問題からやっと開放された、そんな気持ちでいっぱいでした。

A: Submission #3151081 - AtCoder Beginner Contest 109
B: Submission #3165977 - AtCoder Beginner Contest 109
B(コンテスト中の赤黒木バージョン): Submission #3152791 - AtCoder Beginner Contest 109
C: Submission #3165996 - AtCoder Beginner Contest 109
D: Submission #3157410 - AtCoder Beginner Contest 109

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