2019-02-13

「みんなのプロコン 2019」の解説

A - Anti-Adjacency

入力: $N\ K$
出力: $1$ 以上 $N$ 以下の異なる整数を、差が $1$ の整数をともに選ばないように $K$ 個選ぶことができるなら'YES'、そうでないなら'NO'
制約:

$1 \le N, K \le 100$
$N, K \in \mathbb{Z}$

この問題の一番難しいところは、'Yes'ではなくて'YES'と出力するところです(間違いないね)

… 差が1の整数を選んではいけないので、間をはさみながら整数を選んでいくイメージです。
入力例1では、1以上3以下の異なる整数を、差が1の整数をともに選ばないように選べるか(つまり1,2とか2,3ではなく、1,3のように選べるか)と聞いていますが、これは可能です。

しかしながら、入力例2では不可能になります(どうあがいても、1,2,3,4,5の並びしかない)

$1,2,3,\cdots,N$ と続くなかでこの条件を満たして選べる整数の数の限界は $\displaystyle{\left\lfloor{\frac{{{N}+{1}}}{{2}}}\right\rfloor}$ です。

writeln((N + 1) / 2 >= K ? "YES" : "NO");

感想: 'Yes'と'YES'の統一を、どうかお願いします、AtCoder様…(1WA)

B - Path

入力:
$a_1\ b_1$
$a_2\ b_2$
$a_3\ b_3$
出力: すべての道をちょうど1回ずつ通ることですべての街を訪れることが可能ならば'YES'、そうでないなら'NO'
制約:

$1 \le a_i, b_i \le 4(1 \le i \le 3)$
$a_i \ne b_i(1 \le i \le 3)$
同じ街の対の間を結ぶ道は複数存在しない
どの2つの街の間も、道を何本か通ることで行き来することができる

3つの道の様子を追ってみると、始点と終点の番号が1回、それ以外の点は2回だけ出力に現れればよいことがわかります。
これを満たすかどうかを判定すればよいです。

int[] arr;
foreach(_; 0..3) {
	auto ip = readAs!(int[]), a = ip[0], b = ip[1];
	arr ~= a; arr ~= b;
}
arr.sort();
auto a = arr.group();
auto b = a.map!(i => i[1]);
if(b.count(2) == 2 && b.count(1) == 2) {
	writeln("YES");
} else writeln("NO");

感想: 割と面倒なコードを書いてしまった

C - When I hit my pocket...

入力: $K\ A\ B$
出力: $K$ 回の操作の後、すぬけ君が持っているビスケットの枚数の最大値
制約:

$1 \le K, A, B \le 10^9$
$K, A, B \in \mathbb{Z}$

まず、操作の中で「1枚増やす」というものがあります。
また、「A枚のビスケットを1円に交換する」「1円をB枚のビスケットに交換する」という操作もあります。

ここで、 $K+1 < A$ のとき、下二つの操作には関与できないので、すぬけ君はビスケットを叩き続けることしかできません。よって、出力は $K+1$ となります。
そうでないとき、まずポケットを $A-1$ 回叩いてビスケットを $A$ 枚にし、次にビスケット $A$ 枚を $1$ 円に交換し、 $1$ 円をビスケット $B$ 枚に交換することを考えます。

この「ビスケット $A$ 枚から $1円$ $\rightarrow$ $1$ 円からビスケット $B$ 枚」という交換術は、2回の操作が必要です。したがって、この交換術での増分が2以下のとき、わざわざこんなことをする必要もなく、またしてもすぬけ君はビスケットを叩き続けるほうが良いことがわかります。よって出力は $K+1$ になります。
そうでないとき、この交換術では $B-A$ 枚ずつ増えていくので、残りの操作回数の偶奇に注意してコードを書きます。(2回ずつの操作をセットとして考えるので、1回あまったらビスケットを最後に叩く)

auto ip = readAs!(long[]), K = ip[0], A = ip[1], B = ip[2];
// ulongだとB-Aでオーバーフローすることがあるので注意
if(K+1 < A || B - A <= 2) {
	writeln(K+1);
	return;
}
K -= A-1;
writeln((B-A) * (K/2) + K%2 + A);

感想: コンテスト中はもっと無駄にwhile使ったりして頑張ってた $\displaystyle{O}{\left( \log{{K}}\right)}$ 的解法だったけど、実際数学なので $O(1)$ で解けたなあというお気持ち

D - Ears

入力:
$L$
$A_1$
$\vdots$
$A_L$
出力: 必要な操作の回数の最小値
制約:

$1 \le L \le 2 \times 10^5$
$0 \le A_i \le 10^9(1 \le i \le L)$
$L, A_1, \cdots, A_L \in \mathbb{Z}$

コンテスト中に解けなかったので、公式解説の解法を書きます。
数直線上を散歩することについて考えます。
座標 $S$ で散歩を開始し、座標 $T$ で終了したとし、また散歩中に訪れた左端の座標を $D$ 、右端を $U$ とすると、

$i \le D$ 散歩にこない
$D < i \le S$ 散歩にくる。偶数個の石を得る(0でない)
$S < i \le T$ 散歩にくる。奇数個の石を得る
$T < i \le U$ 散歩にくる。偶数個の石を得る(0でない)
$U < i$ 散歩にこない

の5つの区間が考えられます。(0でない、とするところが0だったら前後との区間の区別ができないので、こういう制約をつけます)

ここで、いい感じにそれぞれの区間の切れ目を全探索すればいけそうって感じますが、それをすると制約からしてTLEは不可避です。したがってDPすることを考えます(DはDPのD)

dp[i][j] を、「マス $i$ 以前まで考えた状態で、マス $i$ を含む区間が $j$ になっているときの操作回数の最小値」とします。

また、cost(i, j)を「マス $i$ が区間 $j$ に含まれると考えたときにプラスされる操作回数」とします。

そうすると、
$j \le k$ として
dp[i+1][k] = min(dp[i+1][k], dp[i][j] + calc(i, k))
という遷移を考えることができます。

最後のマス $L$ は区間0〜4のいずれかに含まれるので、出力はdp[L].reduce!minです。

ulong[] A;

ulong cost(ulong i, ulong j) {
	switch(j) {
		case 0, 4:
			return A[i];
		case 1, 3:
			return A[i] == 0 ? 2 : A[i] % 2;
		case 2:
			return (A[i] + 1) % 2;
		default: return 0;
	}
}

void main() {
	auto L = ri;
	A = L.iota.map!(i => readAs!ulong).array;
	auto dp = new ulong[][](L+1, 5);
	foreach(ref v; dp) v[] = INF;
	dp[0][0] = 0;
	foreach(i; 0..L) foreach(j; 0..5) foreach(k; j..5) {
		dp[i+1][k] = min(dp[i+1][k], dp[i][j] + cost(i, k));
	}
	dp[L].reduce!min.writeln;
}

感想: DP難しいけど、理解した後ならよくわかった。

A: Submission #4204208 - Yahoo Programming Contest 2019
B: Submission #4206354 - Yahoo Programming Contest 2019
C: Submission #4251750 - Yahoo Programming Contest 2019
C(コンテスト中): Submission #4212040 - Yahoo Programming Contest 2019
D: Submission #4251409 - Yahoo Programming Contest 2019

2019-02-06

AtCoder Beginner Contest 117の解説

A - Entrance Examination

入力: $T\ X$
出力: 世界Aで実際に進んでいる時間(絶対誤差と相対誤差は $10^{-3}$ 以下である必要がある)
制約:
$1 \le T \le 100$
$1 \le X \le 100$

サンプルでエスパーしましょう(は?)

writefln("%.6f", T / X);

感想: エスパー

B - Polygon

入力:
$N$
$L_1\ L_2\ \ldots L_N$
出力: $N$ 角形が描けるなら'Yes'、そうでないなら'No'
制約:
$3 \le N \le 10$
$1 \le L_i \le 100$

問題文に定理が書かれているので、これを参考にして実装します。
具体的には、 $L_1, L_2, \ldots, L_N$ の総和をとり、一番長い辺の長さをそこから引いたものが、一番長い辺より真に大きいなら'Yes'、そうでないなら'No'と出力すればよいです。

if(L.reduce!max < L.sum - L.reduce!max) {
	writeln("Yes");
} else writeln("No");

感想: 定理が書かれてなかったら、めっちゃ点数上がってそうな気がした。

C - Streamline

入力:
$N\ M$
$X_1\ X_2\ \ldots\ X_M$
出力: 目的を達成するまでに移動を行う回数の最小値
制約:
$1 \le N \le 10^5$
$1 \le M \le 10^5$
$-10^5 \le X_i \le 10^5$
$\displaystyle\forall{i},{j}{\left({\left({i}\ne{j}\right)}\Rightarrow{\left({X}_{{i}}\ne{X}_{{j}}\right)}\right)}$

移動と言っているので、まずXをソートし、 $\displaystyle{i}{\left({0}\le{i}<{N}-{1}\right)}$ について $\displaystyle{X}_{{{i}+{1}}}-{X}_{{i}}$ な数列を考えたくなります。
$N \ge M$ のときは、 $N$ 個のコマによって $M$ 個の座標に訪れてしまうことが可能なので、この場合は0と出力すればよいです。

そうでないときは、1個以上のコマを移動する必要があります。

このとき、考えた数列について、大きい順から $N$ 要素の総和をとり、 $X$ の最大値と最小値の差からその総和を引けば、求める操作回数がわかります。

X.sort();
auto arr = new int[](M-1);
foreach(i; 0..M-1) arr[i] = abs(X[i+1] - X[i]);
//X.writeln;
//arr.writeln;
arr.sort!"a > b"();
long tmp;
if(N >= M) {
	writeln(0);
	return;
}
foreach(i; arr[0..N-1]) {
	tmp += i;
}
//tmp.writeln;
writeln(abs(X.reduce!max - X.reduce!min) - tmp);

感想: こういう問題、入力例から何となく解法を考えるのが大事な気がする

D - XXOR

入力:
$N\ K$
$A_1\ A_2\ \ldots\ A_N$
出力: $f$ の最大値
制約:
$1 \le N \le 10^5$
$0 \le K \le 10^{12}$
$0 \le A_i \le 10^{12}$

公式解説を読めばわかりますが、難しいので、1から理解した自分が書いてみます。

まず、これは質問ですが、 $30213$ と $40214$ はどちらが大きいでしょうか?
当然 $40214$ ですが、あなたはどのようにして大小を比較したでしょうか。
きっと、5桁目が $3 < 4$ だからすぐにわかったのだろうと思います。

では、 $(10101)_2$ と $(11010)_2$ は、どちらが大きいでしょうか?
これは $(11010)_2$ ですね。5桁目はどちらも $1$ なのでまだ大小が確定していませんが、4桁目を見ると $0 < 1$ より大小が確定します。公式解説では、このことを小難しい書きかたで表わしています。(雰囲気はこんな感じなはず)

この問題では、 $X \le K$ なる $X$ について $\displaystyle f{{\left({X}\right)}}=\sum_{{i}}{\left({X}\ \text{ xor }\ {A}_{{i}}\right)}$ としています。

$X \le K$ なので、この条件を満たしている状態を考えて、 $X$ の値を考えてみます。

$X = K$ のとき、特に何も考えず $f(K)$ を求めてみるとよいです。
そうでないとき、Kの2進法表記を考えてみます。
$X < K$ が確定するのは、XとKの二進法表記を上から見ていって、あるところで $0 < 1$ となるときです。
そのため、Kの二進法表記でそこが $1$ であるとき、そこをXの二進法表記で $0$ とすることを考えます。そこの桁を $i$ 桁目とします。
このとき、Xは $i$ より上の桁はKと等しく、 $i$ より下の桁は貪欲に選ぶことができます。
したがって、下のようなコードを書くことになります。なお、 $c_i$ は $i$ 桁目が $1$ である $A$ の要素の個数を表わしています。

auto c = new ulong[](64);
foreach(v; A) foreach(i; v.bitsSet) c[i]++;
ulong res;
if(K == 0) {
	writeln(A.sum);
	return;
}
// X < K のとき
foreach(i; 0..K.log2.ceil.to!ulong) {
	// Kの二進法表記でi桁目が1でなければcontinue(X < Kにしたいので)
	if(!(K & (1UL << i))) continue;
	ulong X = K;
	X &= ~(1UL << i); // Xのi桁目を0にする(i桁目でX < Kを確定させたいので)
	foreach(j; 0..i) {
		if(c[j] > N-c[j]) { // その桁を1にしてxorしたほうが都合がよいのか
			X &= ~(1UL << j);
		} else X |= (1UL << j);
	}
	ulong tmp;
	foreach(v; A) {
		tmp += v ^ X;
	}
	res = max(res, tmp);
}
ulong tmp;
foreach(v; A) { // X = K のとき
	tmp += v ^ K;
}
res = max(res, tmp);
res.writeln;

感想: これを理解したつもりでコードを書くと、X = Kの場合を忘れていてWAを連発したりした。
本番では嘘解法(上から貪欲に決めるとAC)が通るようになっていたのだが、シフト演算に慣れていないせいで1 << aと書いてしまい、1UL << aと書けばパフォ1600だったのに俺は何をオーバーフローさせてんだ…いやでもこれ嘘だしなあ…という微妙な気持ちになった。(どちらかというとレート上昇を逃したのが悔しい)
後日、しっかり本当の解法を理解しようと努めることによって、桁を上から見ることについて少しはわかったのではないかと思う(桁DPで解く方法についても今後考えたい)

A: Submission #4152674 - AtCoder Beginner Contest 117
B: Submission #4153387 - AtCoder Beginner Contest 117
C: Submission #4158140 - AtCoder Beginner Contest 117
D: Submission #4184409 - AtCoder Beginner Contest 117
D(別解法): Submission #4183962 - AtCoder Beginner Contest 117
D(嘘解法): Submission #4167642 - AtCoder Beginner Contest 117

2019-01-12

AISing Programming Contest 2019の解説

A - Bulletin Board

入力:
$N$
$H$
$W$
出力: 貼り出す場所の選び方の場合の数
制約:
$\displaystyle{H},{W},{N}\in\mathbb{Z}$
$\displaystyle{1}\le{H},{W}\le{N}\le{100}$

f:id:private_yusuke:20190112231330p:plain — Aの絵

writeln(max(0, N - H + 1) * max(0, N - W + 1));

感想: これ最初戸惑った。解説は絵を描きたかっただけ。

B - Contests

入力:
$N$
$A\ B$
$\displaystyle{P}_{{1}}\ {P}_{{2}}\ \ldots\ {P}_{{N}}$
$\displaystyle{N},{A},{B},{P}_{{1}},{P}_{{2}},\ldots,{P}_{{N}}\in\mathbb{Z}$
出力: コンテストを実施できる最大の回数
制約:
$\displaystyle{3}\le{N}\le{100}$
$\displaystyle{1}\le{P}_{{i}}\le{20}\ {\left({1}\le{i}\le{N}\right)}$
$\displaystyle{1}\le{A}<{B}<{20}$

問題文より、与えられた問題は3つのパターンに分類することができます。

$\displaystyle{P}_{{i}}\le{A}$
$\displaystyle{A}+{1}\le{P}_{{i}}\le{B}$
$\displaystyle{B}+{1}\le{P}_{{i}}$

一度のコンテストでは、それぞれの分け方から一問ずつ出題されるため、どんどん消費されていきます。
したがって、一番最初に消費しきってしまうグループの値を出力すればよいです。

ulong a = P.filter!(i => i <= A).array.length;
ulong b = P.filter!(i => A+1 <= i && i <= B).array.length;
ulong c = P.filter!(i => i >= B + 1).array.length;
writeln(min(a, b, c));

感想: なぜか問題を読むのに時間がかかった。風呂上がって髪を乾かした後、もう20秒しかない状態でコンテストに参加したので、10分ぐらい上裸だった。そんな状況でACできたので自分を称えたい(は?)

C - Alternating Path

入力:
$H\ W$
$S_1$
$S_2$
$\vdots$
$S_H$
出力: 条件を満たすものの個数
制約:
$\displaystyle{1}\le{H},{W}\le{400}$
$\displaystyle{\left|{S}_{{i}}\right|}={W}\ {\left({1}\le{i}\le{H}\right)}$
各 $\displaystyle{i}\ {\left({1}\le{i}\le{H}\right)}$ に対して、文字列 $S_i$ は文字'#'と文字'.'だけからなる。

まず、愚直に全探索することを考えてみる( $\displaystyle{\left({a},{b}\right)}\to{\left({c},{d}\right)}$ の移動を、すべての $a,b,c,d$ について考える)と、 $\displaystyle\text{O}{\left({W}^{2}{H}^{2}\right)}$ で $\displaystyle{400}^{4}={25600000000}$ となり、 $\displaystyle{{\log}_{{10}}{\left({25600000000}\right)}}\approx{10.4082399653}$ なので間に合いません。
したがって、どうにか計算量を落としたい気持ちになります。
ここで、入力例 1を画像にしてみると、こんな感じになります。

f:id:private_yusuke:20190112233125p:plain — Bの絵1

それぞれの'#'から、隣りあった'.'に行けることは問題文からわかります。
問われているのは、'#'から'.'に行ける場合の数です。

f:id:private_yusuke:20190112233615p:plain — Bの絵2

例えば、こういうふうに $\displaystyle{\left({1},{2}\right)}\to{\left({3},{3}\right)}$ と行くことができます。

f:id:private_yusuke:20190112235228p:plain — Bの絵3

こうやって見ると、通うことのできる範囲にある'#'と'.'の個数をかけ算すればよくね?ということに気づきます。これは考えてみるとわかります。
よって、まずは'#'のあるところの座標から探索することにします。
そして、それぞれ問題文の条件を満たすようにDFSで探索し、通うことのできる範囲をしらみつぶしに調べます。その間に計算した座標については訪問済みフラグを立てておき、次は計算をしないように管理します(これで計算量が減ります)。
こうすることで、 $\displaystyle\text{O}{\left({H}{W}\right)}$ で計算が終わります。よってTLEを防ぐことができました。

int[] dy = [1, 0, -1, 0], dx = [0, 1, 0, -1];
Pair[] stack;
foreach(i, iv; S) foreach(j, jv; iv) {
	if(jv == '#') stack ~= Pair(i, j);
}
ulong res;
bool[][] done = new bool[][](H, W);

//ulong res2;
while(stack != []) {
	auto p = stack.front;
	stack.popFront;
	if(done[p.y][p.x]) continue; // 計算量が減るポイント
	Pair[] stack2;
	stack2 ~= Pair(p.y, p.x);
	ulong wh, bl;
	
	while(stack2 != []) {
		auto p2 = stack2.front;
		stack2.popFront;

		foreach(k; 0..4) { //周囲4マスを探索します
			auto ry = p2.y + dy[k];
			auto rx = p2.x + dx[k];
			if(0 <= ry && ry < H && 0 <= rx && rx < W && S[ry][rx] != S[p2.y][p2.x] && !done[ry][rx]) {
				if(S[ry][rx] == '.') { res++; wh++; }
				else bl++;
				stack2 ~= Pair(ry, rx);
				done[ry][rx] = true;
			}
		}
		done[p2.y][p2.x] = true;
	}
	res += wh * bl; // 通える範囲にある'#'と'.'の個数の積をとり答に加算する
}
res.writeln;

感想: この発想が出て30分は、結局 $\displaystyle\text{O}{\left({H}^{2}{W}^{2}\right)}$ になってしまう別のコードを書いてしまい、学校の競プロerに抜かされてしまった。悔しい。でも解けたのでオッケーです

D とか

読んでない

A: Submission #3983758 - AISing Programming Contest 2019 / エイシングプログラミングコンテスト 2019
B: Submission #3985570 - AISing Programming Contest 2019 / エイシングプログラミングコンテスト 2019
C: Submission #3990879 - AISing Programming Contest 2019 / エイシングプログラミングコンテスト 2019

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