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

A - Changing a Character

入力:
$N\ K$
$S$
出力: 新しくできた $S$
制約:

$1 \le N \le 50$
$1 \le K \le N$
$S$ は'A', 'B', 'C'からなる長さ $N$ の文字列

A, B, Cをそれぞれa, b, cに変換する関数を作ってあげればよいです。

void main() {
	auto ip = readAs!(int[]), N = ip[0], K = ip[1];
	auto S = rs;
	writeln(S[0..K-1] ~ f(S[K-1]) ~ S[K..$]);
}
 
char f(char x) {
	switch (x) {
		case 'A': return 'a';
		case 'B': return 'b';
		case 'C': return 'c';
		default: return '1';
	}
}

こんな手間をかけなくても、標準ライブラリに入力された文字列に含まれる大文字を小文字に変換する関数が用意されていると思いますので、思いつく人はそちらを使うと良いと思います。

感想: 調べるのがめんどくさかったのでfを実装してしまった。

B - YYMM or MMYY

入力: $S$
出力: 'YYMM', 'MMYY', 'AMBIGUOUS' , 'NA' のいずれか
制約:

$S$ は長さ $4$ の数字列

Sを"○○××"と表わしたとします。
"○○"が1から12の数字なら'MMYY'の可能性があります。
"××"が1から12の数字なら'YYMM'の可能性があります。

どちらの可能性もあるならば'AMBIGUOUS'、どちらの可能性もないならば'NA'となります。

int i = S[0..2].to!int;
int j = S[2..$].to!int;
bool YYMM = j <= 12 && 1 <= j;
bool MMYY = i <= 12 && 1 <= i;
if(YYMM && MMYY) writeln("AMBIGUOUS");
else if(YYMM) writeln("YYMM");
else if(MMYY) writeln("MMYY");
else writeln("NA");

感想: タイピングゲーム

C - Dice and Coin

入力: $N\ K$
出力: すぬけ君が勝つ確率
制約:

$1 \le N \le 10^5$
$1 \le K \le 10^5$

問題文より、 $N$ 面サイコロからは、 $1 \le i \le N$ であるような $i$ それぞれの数字が出ます。
したがって、出た目が $i$ のときを考えます。

条件より、勝つためにはコインの表を出し続けることが必要です。では、何回コインの表を出せば勝てるのでしょうか?

これを考えると、 $\displaystyle{i}\cdot{2}^{j}\ge{K}$ をみたす最小のjだけコインの表を出せばいいことがわかります。
両辺の、底が2の対数をとると
$\displaystyle{{\log}_{{2}}{\left({i}\cdot{2}^{j}\right)}}\ge{{\log}_{{2}}{K}}$
$\displaystyle{{\log}_{{2}}{\left({i}\right)}}+{{\log}_{{2}}{\left({2}^{j}\right)}}\ge{{\log}_{{2}}{\left({K}\right)}}$
$\displaystyle{{\log}_{{2}}{\left({i}\right)}}+{j}\ge{{\log}_{{2}}{\left({K}\right)}}$
$\displaystyle{j}\ge{{\log}_{{2}}{\left({K}\right)}}-{{\log}_{{2}}{\left({i}\right)}}$
したがって、これを満たす最小のjの値は $\displaystyle{j}=\text{ceil}{\left({{\log}_{{2}}{\left({K}\right)}}-{{\log}_{{2}}{\left({i}\right)}}\right)}$ です。

ただし、 $K \le i$ であるような場合に注意する必要があります。なぜなら、この場合はコインを振る前にすでにすぬけ君は勝利しているからです。

double p = 0;
foreach(i; 1..N+1) {
	auto j = ceil(log2(K) - log2(i));
	if(i >= K) j = 0;
	double tmp = 1./N * pow(1/2., j);
	p += tmp;
	//tmp.writeln;
}
writefln("%.10f", p);

感想: 式変形を考察用紙でするのが楽しかった。i >= Kであるときに注意。

D - Even Relation

入力:
$N$
$u_1\ v_1\ w_1$
$u_2\ v_2\ w_2$
$\vdots$
$u_{N-1}\ v_{N-1}\ w_{N-1}$
出力: 条件を満たす塗り分け方
制約:

入力は全て整数である。
$1 \le N \le 10^5$
$1 \le u_i < v_i \le N$
$1 \le w_i \le 10^9$

与えられるグラフが木であることに着目しましょう。このような場合は、DFSやBFSによる探索がしやすいです。
一度探索した頂点はもう一度検証しないように注意しましょう。

最初に訪れる頂点はvisitableとします。

ある頂点 $P$ に着目するとき、隣りあった頂点 $Q$ について、 $PQ$ 間の距離を $d$ とおくと
i) $P$ がvisitableであるかつ dが偶数 -> $Q$ はvisitableである
ii) $P$ がvisitableであるかつ dが奇数 -> $Q$ はvisitableでない
iii) $P$ がvisitableでないかつ dが偶数 -> $Q$ はvisitableでない
iv) $P$ がvisitableでないかつ dが奇数 -> $Q$ はvisitableである

というふうに考えると、visitableであるか否かを参考にしてグラフの色分けをすることができます。

alias Pair = Tuple!(int, "u", int, "v", int, "w");
Pair[] pairs;
Pair[][long] next;
foreach(i; 0..N-1) {
	auto ip = readAs!(int[]), u = ip[0], v = ip[1], w = ip[2];
	pairs ~= Pair(u-1, v-1, w);
	pairs ~= Pair(v-1, u-1, w);
	next[u-1] ~= Pair(u-1, v-1, w);
	next[v-1] ~= Pair(v-1, u-1, w);
}
auto visitable = new bool[](N);
auto visited = new bool[](N);
visitable[0] = true;
long[] queue = [0];

while(queue != []) {
	long i = queue.front;
	queue.popFront;
	if(visited[i]) continue;
	visited[i] = true;
	//i.writeln;
	
	foreach(v; next.get(i, [])) {
		//v.writeln;
		if(((visitable[i] ? 0 : 1) + v.w) % 2 == 0) visitable[v.v] = true;
		else visitable[v.v] = false;
		if(!visited[v.v]) queue ~= v.v;
	}
}
//visitable.writeln;
visitable.map!(i => i ? 0 : 1).each!writeln;

感想: 実装もうちょっとどうにかなりそう

E - 1 or 2

入力:
$N\ M$
$X_1\ Y_1\ Z_1$
$X_2\ Y_2\ Z_2$
$\vdots$
$X_M\ Y_M\ Z_M$
出力: 必要なコストの最小値
制約:

入力は全て整数である。
$2 \le N \le 10^5$
$1 \le M \le 10^5$
$1 \le X_i < Y_i \le N$
$1 \le Z_i \le 100$
$(X_i, Y_i)$ の組は互いに異なる。
与えられる入力には矛盾がない(すなわち、条件を満たす $A_1, A_2, \dots, A_N$ が存在する)。

入力では $A_{X_i} + A_{Y_i} + Z_i$ は偶数である、という情報が与えられる。

ここで、2つの整数 $A, B$ について考えてみる。
i) $A$ が奇数で $B$ も奇数のとき $A+B$ は偶数
ii) $A$ が奇数で $B$ が偶数のとき $A+B$ は奇数
iii) $A$ が偶数で $B$ が奇数のとき $A+B$ は奇数
iv) $A$ が偶数で $B$ が偶数のとき $A+B$ は偶数

入力で与えられる $Z_i$ には何の意味もない。
ここで注目したいのが、 $A,B$ のどちらかの偶奇がわかれば、もう片方の偶奇もわかるということ。
だから、 $A,B,C$ のような3つの整数があったとき、入力でそれぞれつながっているような情報が与えられたならば(例えば $A+B$ と $B+C$ の情報とか、 $A+C$ と $A+B$ の情報など)その塊のうちのどれか一つの数の偶奇が判明すればドミノ倒しのように他の整数の偶奇も判明する。

したがって、与えられる $X_i, Y_i$ の組をグラフの辺と考えて、そのグラフの中にある連結成分の数がそのまま答えになる。
これは、UnionFindやDFSなどが有効に利用できる。この解答ではUnionFindを使うことにする。

auto ip = readAs!(int[]), N = ip[0], M = ip[1];
auto uf = new UnionFind!long(N);
foreach(i; 0..M) {
	auto ip2 = readAs!(int[]), X = ip2[0], Y = ip2[1], Z = ip2[2];
	uf.unite(X-1, Y-1);
}
N.iota.map!(i => uf.root(i) == i).sum.writeln;

UnionFindを使うとき、連結成分の数は、頂点の番号と、その頂点の根の番号が一致する場合の数に等しい。

感想: 終了2分前にこの解法に気づいたが、UFでの連結成分の数え方を知らなかったので提出できなかった。

A: Submission #5448688 - AtCoder Beginner Contest 126
B: Submission #5450291 - AtCoder Beginner Contest 126
C: Submission #5457149 - AtCoder Beginner Contest 126
D: Submission #5468811 - AtCoder Beginner Contest 126
E: Submission #5481438 - AtCoder Beginner Contest 126