AtCoder Beginner Contest 126 - 情報妖精の競プロ日記

AtCoder Beginner Contest 126 (ABC126)に参加しました！

解けた問題だけ解説をしていきますー

要項

AtCoder Beginner Contest 126
rated 1999 → unrated
5/19(日) 21:00 ～ 22:40 (100分)
100-200-300-400-500-600 (6問)
ペナルティ: 5分

方針

全完一択でしょ
久しぶりにブログも書きたい(ごめんね？)ので、もちろん全部解いて投稿します。

A - Changing a Character

問題文

問題文
A, B, C からなる長さ $N$ の文字列 $S$ と、 $1$ 以上 $N$ 以下の整数 $K$ が与えられます。文字列 $S$ の $K$ 文字目を小文字に書き換え、新しくできた $S$ を出力してください。
制約

$1 \leq N \leq 50$

$1 \leq K \leq N$

$S$ は A, B, C からなる長さ $N$ の文字列

大文字を小文字に変更するとき、大文字のアルファベットや小文字のアルファベットが同じように文字コード内で連続していることを利用して、A-aを引いてあげれば変更できます。
後は該当文字を変更する方法ですが、それはそのまま $K$ 番目の文字に変更を書ければいいです。

ソースコード(C++)

#include<iostream>
using namespace std;
int main() {
	int N, K;
	string S;
	cin >> N >> K >> S;
	S[K - 1] -= 'A' - 'a';
	cout << S;
	return 0;
}

ソースコード(Java)

import java.util.Scanner;
public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int N = sc.nextInt(), K = sc.nextInt();
		char[] S = sc.next().toCharArray();
		S[K - 1] -= 'A' - 'a';
		System.out.println(String.valueOf(S));
	}
}

ソースコード(Python)

N, K = map(int, input().split(" "))
S = input()
print(S[:K-1] + S[K - 1].lower() + S[K:])

B - YYMM or MMYY

問題文

問題文
長さ $4$ の数字列 $S$ が与えられます。あなたは、この数字列が以下のフォーマットのどちらであるか気になっています。

YYMM フォーマット: 西暦年の下 $2$ 桁と、月を $2$ 桁で表したもの (例えば $1$ 月なら 01) をこの順に並べたもの

MMYY フォーマット: 月を $2$ 桁で表したもの (例えば $1$ 月なら 01) と、西暦年の下 $2$ 桁をこの順に並べたもの

与えられた数字列のフォーマットとして考えられるものが YYMM フォーマットのみである場合 YYMM を、MMYY フォーマットのみである場合 MMYY を、YYMM フォーマットと MMYY フォーマットのどちらの可能性もある場合 AMBIGUOUS を、どちらの可能性もない場合 NA を出力してください。
制約

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

ひたすらに面倒なだけの問題ですね……。
まず、先頭2文字と後方2文字がそれぞれ月フォーマットに一致するか、すなわち $1$ 以上 $12$ 以下かを判定します。
後はそれぞれの判定結果で4通りに分岐するので、それぞれ問題文の通りに出力すれば良いです。

ソースコード(C++)

#include<iostream>
using namespace std;
int main() {
	int S;
	cin >> S;
	bool l = 1 <= S / 100 && S / 100 <= 12, r = 1 <= S % 100 && S % 100 <= 12;
	if (l && r) cout << "AMBIGUOUS" << endl;
	else if (l && !r) cout << "MMYY" << endl;
	else if (!l && r) cout << "YYMM" << endl;
	else cout << "NA" << endl;
	return 0;
}

ソースコード(Java)

import java.util.Scanner;
public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int S = sc.nextInt();
		boolean l = 1 <= S / 100 && S / 100 <= 12, r = 1 <= S % 100 && S % 100 <= 12;
		if (l && r) System.out.println("AMBIGUOUS");
		else if (l && !r) System.out.println("MMYY");
		else if (!l && r) System.out.println("YYMM");
		else System.out.println("NA");
	}
}

ソースコード(Python)

S = int(input())
if 1 <= S / 100 and S / 100 <= 12:
	if 1 <= S % 100 and S % 100 <= 12: print("AMBIGUOUS")
	else: print("MMYY")
else:
	if 1 <= S % 100 and S % 100 <= 12: print("YYMM")
	else: print("NA")

C - Dice and Coin

問題文

問題文
すぬけ君は $1$ 〜 $N$ の整数が等確率で出る $N$ 面サイコロと表と裏が等確率で出るコインを持っています。すぬけ君は、このサイコロとコインを使って今から次のようなゲームをします。

まず、サイコロを $1$ 回振り、出た目を現在の得点とする。

得点が $1$ 以上 $K-1$ 以下である限り、すぬけ君はコインを振り続ける。表が出たら得点は $2$ 倍になり、裏が出たら得点は $0$ になる。

得点が $0$ になった、もしくは $K$ 以上になった時点でゲームが終了する。このとき、得点が $K$ 以上である場合すぬけ君の勝ち、 $0$ である場合すぬけ君の負けである。

$N$ と $K$ が与えられるので、このゲームですぬけ君が勝つ確率を求めてください。
制約

$1 ≤ N ≤ 10^5$

$1 ≤ K ≤ 10^5$

入力はすべて整数

まず、サイコロの出目に応じて初期の得点が決まります。
出目が出る範囲の初期値が $\frac{1}{N}$ 、出ない範囲の初期値が $0$ ですね。
次に、得点が減ることはないので小さい方から見ていくと、各得点について素直に遷移が書けることが分かります。
すなわち、配るDPをするとそのままそれが答えになります。
なお、得点が $K$ 以上となっているので、 $K$ 以上になるようなものを全て $K$ に遷移するように読み替えると答えが出しやすくなります。

ソースコード(C++)

#include<iostream>
#include<iomanip>
using namespace std;
int main() {
	int N, K;
	cin >> N >> K;
	double dp[100001] = {};
	for (int i = 1;i <= min(K, N);++ i) dp[i] += 1.0 / N;
	dp[K] += (double)max(0, N - K) / N;
	for (int i = 1;i < K;++ i) dp[min(K, 2 * i)] += dp[i] / 2;
	cout << setprecision(10) << fixed << dp[K] << endl;
	return 0;
}

ソースコード(Java)

import java.util.Scanner;
import java.util.Arrays;
public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int N = sc.nextInt(), K = sc.nextInt();
		double[] dp = new double[K + 1];
		Arrays.fill(dp, 0);
		for (int i = 1;i <= Math.min(N, K);++ i) dp[i] = 1.0 / N;
		dp[K] += (double)Math.max(0, N - K) / N;
		for (int i = 1;i < K;++ i) dp[Math.min(i * 2, K)] += dp[i] / 2;
		System.out.println(dp[K]);
	}
}

D - Even Relation

問題文

問題文
$N$ 頂点の木があります。この木の $i$ 番目の辺は頂点 $u_i$ と頂点 $v_i$ を結んでおり、その長さは $w_i$ です。あなたは以下の条件を満たすように、この木の頂点を白と黒の $2$ 色で塗り分けたいです (すべての頂点を同じ色で塗っても構いません)。

同じ色に塗られた任意の $2$ 頂点について、その距離が偶数である。

条件を満たす塗り分け方を $1$ つ見つけて出力してください。この問題の制約下では、そのような塗り分け方が必ず $1$ つは存在することが証明できます。
制約

入力は全て整数である。

$1 \leq N \leq 10^5$

$1 \leq u_i < v_i \leq N$

$1 \leq w_i \leq 10^9$

まず、頂点を一つ決め打ち、その頂点の色が白色としても一般性を失いません。(仮にその頂点が黒色の場合の答えがあるとして、全ての色を反転させた木もまた正しいので)
すると、その頂点から偶数の距離にある頂点は全て白色です。また、奇数の距離にある頂点は全て黒色です。
問題文より必ず塗り分け方が存在するのでこれを提出して問題ないことは分かりますが、念のため正しいことを証明しましょう。
ある頂点 $A, B, C$ があって、 $A$ から $B$ までの距離と $A$ から $C$ までの距離が分かっているものとします。
この時、 $A$ から $B$ までと $A$ から $C$ までの間に共通の経路があって長さを $d$ とすると、共通の経路を省いた経路(すなわち、 $B$ から $C$ までの経路)は先の距離から $2d$ を引いたものになります。
$2d$ は偶数であり、偶数を引いた距離の偶奇は変わらないので全ての距離はある頂点から見た距離を使って判断しても問題ないことが示せました。
なお、一般のグラフについても二部グラフ判定を用いればこれは求められます。(木は必ず二部グラフです)

ソースコード(C++)

#include<iostream>
#include<vector>
#include<queue>
using namespace std;
int main() {
	int N, u, v, w;
	cin >> N;
	vector<vector<pair<int, int> > > tree(N);
	for (int i = 1;i < N;++ i) {
		cin >> u >> v >> w;
		tree[--u].push_back(make_pair(--v, w & 1));
		tree[v].push_back(make_pair(u, w & 1));
	}
	vector<int> ans(N, -1);
	ans[0] = 0;
	queue<int> que;
	for (que.push(0);!que.empty();que.pop()) {
		int tmp = que.front();
		for (int i = 0;i < tree[tmp].size();++ i) {
			if (ans[tree[tmp][i].first] >= 0) continue; // もう調べた
			ans[tree[tmp][i].first] = ans[tmp] ^ tree[tmp][i].second; // 距離が偶数なら同じ色、奇数なら違う色
			que.push(tree[tmp][i].first);
		}
	}
	for (int i = 0;i < N;++ i) cout << ans[i] << endl;
	return 0;
}

ソースコード(Java)

import java.util.Scanner;
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.Queue;
public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int N = sc.nextInt();
		List<List<Edge>> edge = new ArrayList<>();
		for (int i = 0;i < N;++ i) edge.add(new ArrayList<>());
		for (int i = 1;i < N;++ i) {
			int u = sc.nextInt() - 1, v = sc.nextInt() - 1, w = sc.nextInt();
			edge.get(u).add(new Edge(v, w));
			edge.get(v).add(new Edge(u, w));
		}
		int[] color = new int[N];
		Arrays.fill(color, -1);
		color[0] = 0;
		Queue<Integer> queue = new ArrayDeque<>();
		queue.add(0);
		while (!queue.isEmpty()) {
			int tmp = queue.poll();
			for (Edge i : edge.get(tmp)) {
				if (color[i.edge] >= 0) continue; // もう調べた
				color[i.edge] = color[tmp] ^ (i.weight & 1); // 距離が偶数なら同じ色、奇数なら違う色
				queue.add(i.edge);
			}
		}
		for (int i = 0;i < N;++ i) System.out.println(color[i]);
	}
	public static class Edge {
		int edge;
		int weight;
		public Edge(int edge, int weight) {
			this.edge = edge;
			this.weight = weight;
		}
	}
}

E - 1 or 2

問題文

問題文
$N$ 枚のカードが一列に伏せられており、各カードには整数 $1$ または $2$ が書かれています。
$i$ 番目のカードに書かれている整数を $A_i$ とします。
あなたの目的は $A_1, A_2, ..., A_N$ を当てることです。
次のことが分かっています。

$i = 1, 2, ..., M$ について $A_{X_i} + A_{Y_i} + Z_i$ は偶数である。

あなたは魔法使いです。次の魔法を何度でも使うことができます。
魔法: コストを $1$ 払う。カードを $1$ 枚選び、そのカードに書かれた整数 $A_i$ を知る。
最小で何コスト払えば、 $A_1, A_2, ..., A_N$ 全てを確実に当てることができるでしょうか。
なお、与えられる入力には矛盾がないことが保証されます。
制約

入力は全て整数である。

$2 \leq N \leq 10^5$

$1 \leq M \leq 10^5$

$1 \leq X_i < Y_i \leq N$

$1 \leq Z_i \leq 100$

$(X_i, Y_i)$ の組は互いに異なる。

与えられる入力には矛盾がない(すなわち、条件を満たす $A_1, A_2, ..., A_N$ が存在する)。

まず、 $(X_i, Y_i)$ を辺とするグラフと思って考えます。
明らかに、連結でない部分についてはそれぞれカードの内容を見ないと答えが分かりません。
逆に、連結なグラフにおけるある要素の答えが分かったとします。
すると、方程式を見れば明らかにもう1個は分かるので、結果として連結な全ての要素が分かります。
よって後は連結成分の個数を出力するだけで良いです。
……なんでこれ矛盾が無い入力なんだろ？判定パートが有っても、矛盾を調べるのはそんな難しくないけど……(1個を決め打って矛盾が出ないか調べていくだけ)

ソースコード(C++)

#include<iostream>
#include<vector>
#include<queue>
using namespace std;
int main() {
	int N, M, x, y, z, ans = 0;
	cin >> N >> M;
	vector<vector<int> > graph(N);
	for (int i = 0;i < M;++ i) {
		cin >> x >> y >> z;
		graph[--x].push_back(--y);
		graph[y].push_back(x);
	}
	vector<bool> bfs(N, false);
	queue<int> que;
	for (int i = 0;i < N;++ i) {
		if (bfs[i]) continue; // 調べ終わっている
		bfs[i] = true;
		++ ans;
		for (que.push(i);!que.empty();que.pop()) {
			int tmp = que.front();
			for (int j = 0;j < graph[tmp].size();++ j) {
				if (bfs[graph[tmp][j]]) continue; // 既に色を塗った
				bfs[graph[tmp][j]] = true;
				que.push(graph[tmp][j]);
			}
		}
	}
	cout << ans << endl;
	return 0;
}

ソースコード(Java)

import java.util.Scanner;
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.Queue;
public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int N = sc.nextInt(), M = sc.nextInt();
		List<List<Integer>> graph = new ArrayList<>();
		for (int i = 0;i < N;++ i) graph.add(new ArrayList<>());
		for (int i = 0;i < M;++ i) {
			int x = sc.nextInt() - 1, y = sc.nextInt() - 1, z = sc.nextInt();
			graph.get(x).add(y);
			graph.get(y).add(x);
		}
		int ans = 0;
		boolean bfs[] = new boolean[N];
		Arrays.fill(bfs, false);
		for (int i = 0;i < N;++ i) {
			if (bfs[i]) continue; // 調べ終わっている
			bfs[i] = true;
			++ ans;
			Queue<Integer> queue = new ArrayDeque<>();
			for (queue.add(i);!queue.isEmpty();) {
				int tmp = queue.poll();
				for (int next : graph.get(tmp)) {
					if (bfs[next]) continue; // 既に色を塗った
					bfs[next] = true;
					queue.add(next);
				}
			}
		}
		System.out.println(ans);
	}
}

F - XOR Matching

問題文

以下の条件を満たす、長さ $2^{M + 1}$ の数列 $a$ = { $a_1,\ a_2,\ ...,\ a_{2^{M + 1}}$ } を、存在するならば $1$ つ構築してください。

$a$ は $0$ 以上 $2^M$ 未満の整数を、それぞれちょうど $2$ つずつ含む。

$a_i = a_j$ を満たす任意の $i,\ j \ (i < j)$ について、 $a_i \ xor \ a_{i + 1} \ xor \ ... \ xor \ a_j = K$ である。

xor (排他的論理和) とは

整数 $c_1, c_2, ..., c_n$ の xor は以下のように定義されます。

$c_1 \ xor \ c_2 \ xor \ ... \ xor \ c_n$ を二進表記した際の $2^k$ ( $k \geq 0$ ) の位の数は、 $c_1, c_2, ..., c_n$ のうち二進表記した際の $2^k$ の位の数が $1$ となるものが奇数個ならば $1$ 、偶数個ならば $0$ である。

例えば、 $3 \ xor \ 5 = 6$ です (二進表記すると: 011 $xor$ 101 $=$ 110 です)。

制約

入力は全て整数である。

$0 \leq M \leq 17$

$0 \leq K \leq 10^9$

さて、サンプルより $M=0$ の時の答えは分かっています。
また、排他的論理和ではどうやっても値が元の値より大きな(2進数上での)桁数になることはないので、 $2^M \leq K$ ならば明らかに不可能です。
さて、それ以外の場合はどうなるでしょうか？
実は、これは可能です。
まず、排他的論理和について、次の性質が成り立つことが分かります。

$x \ xor \ y \ xor \ x = y$
$0 \ xor \ x = x$
$0 \ xor \ 1 \ xor \ \cdots \ xor \ 4n = 0$

最後の性質については、 $4n$ から $4n+3$ までの全ての値は2進数における3桁目以降が等しく(つまり、4回 $xor$ を取ると0になる)、下2桁は $0 \ xor \ 1 \ xor \ 2 \ xor \ 3 = 0$ であることから導けます。
従って、 $M \geq 1$ の時は全体の $xor$ は $0$ であり、 $0 \ xor \ 1 \ xor \ \cdots \ xor \ K-1 \ xor \ K+1 \ xor \ \cdots \ xor \ 2^M-1 = K$ であることが分かります。
よって、 $K$ 以外の全ての要素は $K$ を間に挟み、 $K$ はそれ以外の全ての要素を間に挟むような構造を考えることができます。
この時、1番目の性質より次のように構築をすると条件を満たすことが分かります。
$0 \ 1 \ 2 \cdots K-1 \ K+1 \cdots 2^M-1 \ K \ 2^M-1 \cdots K+1 \ K-1 \cdots 2 \ 1 \ 0 \ K$
この時、 $K$ の間には $K$ を除く全ての要素が1個ずつ挟まっているため $xor$ は $K$ になり、それ以外の全ての値の間には $K$ が1個とそれ以外の値のうちいくつかが2個挟まっているため、2個挟まっている値は無視できることから $xor$ は $K$ になるので条件を満たします。
$M=0$ の場合はサンプルに既に答えがあるので、これで全ての答えが網羅できました。

ソースコード(C++)

#include<iostream>
using namespace std;
int main() {
	int M, K;
	cin >> M >> K;
  	M = 1 << M;
	if (K < M && M != 2) {
		for (int i = 0;i < M;++ i) {
			if (i == K) continue;
			cout << i << ' ';
		}
		cout << K << ' ';
		for (int i = M - 1;i >= 0;-- i) {
			if (i == K) continue;
			cout << i << ' ';
		}
		cout << K << endl;
	} else if (M == 2 && K == 0) cout << "0 0 1 1" << endl;
	else cout << -1 << endl;
	return 0;
}

ソースコード(Java)

import java.util.Scanner;
public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int M = 1 << sc.nextInt(), K = sc.nextInt();
		if (K < M && M != 2) {
			for (int i = 0;i < M;++ i) {
				if (i == K) continue;
				System.out.print(i + " ");
			}
			System.out.print(K + " ");
			for (int i = M - 1;i >= 0;-- i) {
				if (i == K) continue;
				System.out.print(i + " ");
			}
			System.out.println(K);
		} else if (M == 2 && K == 0) System.out.println("0 0 1 1"); 
		else System.out.println("-1");
	}
}

結果

oooooo 6完(2100点) 3:56-12:02-19:09-34:12-42:20-79:37(1WA) / 84:37
279位

感想

おおう、全完したのにunratedは辛い……。
今回はジャッジが重く、人によって異なるジャッジ速度だったのがまずかったみたいです。
にしても、配点の割に簡単だったような気がするけど、もう少し難しくても良いのよ？
最後の問題はまぁ面白かったけど、でもやっぱりそこまで難しくはなさげ。