はまやんはまやんはまやん

hamayanhamayan's blog

1 or 2 [AtCoder Beginner Contest 126 E]

https://atcoder.jp/contests/abc126/tasks/abc126_e

前提知識

解説

https://atcoder.jp/contests/abc126/submissions/5476491

入力には矛盾が無いということが使える。
あるiについて、Axi+Ayi+Ziが偶数であることが分かるとき、xiとyiに辺を張ることを考える。
この辺の意味は片方がわかれば、もう片方も分かるという意味である。
このルールで辺を貼っていくと、無向グラフができあがる。
この無向グラフの連結成分について、1つでも数がわかれば全ての数が特定できる。
つまり、連結成分の数が答えになっている。

連結成分を探すのはUnionFindを使えばいいので、使って連結成分数を数えると答え。

int N, M;
//---------------------------------------------------------------------------------------------------
void _main() {
	cin >> N >> M;
	UnionFind uf(N);
	rep(i, 0, M) {
		int x, y, z; cin >> x >> y >> z;
		x--; y--;
		uf(x, y);
	}
 
	int ans = 0;
	rep(i, 0, N) if (uf[i] == i) ans++;
	cout << ans << endl;
}

Even Relation [AtCoder Beginner Contest 126 D]

https://atcoder.jp/contests/abc126/tasks/abc126_d

解説

https://atcoder.jp/contests/abc126/submissions/5477114

以下のルールで着色していく。
辺の長さが偶数なら2つの頂点は同じ色で着色する。
辺の長さが奇数なら2つの頂点は異なる色で着色する。
 
これを守ってDFSで着色すれば答えが求まる。

int N;
vector<pair<int, int>> E[101010];
//---------------------------------------------------------------------------------------------------
int ans[101010];
void dfs(int cu, int pa = -1, int col = 0) {
	ans[cu] = col;
	fore(p, E[cu]) {
		if (p.first == pa) continue;
 
		if (p.second % 2 == 0) dfs(p.first, cu, col);
		else dfs(p.first, cu, 1 - col);
	}
}
//---------------------------------------------------------------------------------------------------
void _main() {
	cin >> N;
	rep(i, 0, N - 1) {
		int a, b, c; cin >> a >> b >> c;
		a--; b--;
 
		E[a].push_back({ b,c });
		E[b].push_back({ a,c });
	}
 
	dfs(0);
 
	rep(i, 0, N) printf("%d\n", ans[i]);
}

Dice and Coin [AtCoder Beginner Contest 126 C]

https://atcoder.jp/contests/abc126/tasks/abc126_c

解説

https://atcoder.jp/contests/abc126/submissions/5476041

シミュレーションしながら、答えを導いていこう。
サイコロで[1,N]のどれが出るかを全探索しよう。
そこから、コインを振って、得点が倍になる場合に限って確率を求める。
最初のサイコロで出る値で全探索すれば、排反なので、総和を取ると答え。

int N, K;
//---------------------------------------------------------------------------------------------------
void _main() {
	cin >> N >> K;
 
	double ans = 0;
	rep(x, 1, N + 1) {
		int y = x;
		double q = 1.0 / N;
		while (y < K) {
			y *= 2;
			q /= 2;
		}
		ans += q;
	}
	printf("%.10f\n", ans);
}

YYMM or MMYY [AtCoder Beginner Contest 126 B]

https://atcoder.jp/contests/abc126/tasks/abc126_b

解説

https://atcoder.jp/contests/abc126/submissions/5475422

上2つを数値にしたものをa, 下2つを数値にしたものをbとする。
この変換は数字-'0'をすると、文字を数値化できることを利用する。
 
あとは、YYMMフォーマットかどうか、MMYYフォーマットかどうかを
チェックして、それを使って出力を分ければいい。

string S;
//---------------------------------------------------------------------------------------------------
void _main() {
	cin >> S;
 
	int a = (S[0] - '0') * 10 + S[1] - '0';
	int b = (S[2] - '0') * 10 + S[3] - '0';
 
	bool YYMM = false;
	if (1 <= b and b <= 12) YYMM = true;
	bool MMYY = false;
	if (1 <= a and a <= 12) MMYY = true;
 
	if (YYMM and MMYY) cout << "AMBIGUOUS" << endl;
	else if (YYMM) cout << "YYMM" << endl;
	else if (MMYY) cout << "MMYY" << endl;
	else cout << "NA" << endl;
}

Changing a Character [AtCoder Beginner Contest 126 A]

https://atcoder.jp/contests/abc126/tasks/abc126_a

解説

https://atcoder.jp/contests/abc126/submissions/5474925

Aをaに変換することを考える。
A + x = a
x = a - A
という感じにAにxを足すとaにできる。
この関係はBからb, Cからcも同様であるため、この差分を足せば小文字にできる。

int N, K; string S;
//---------------------------------------------------------------------------------------------------
void _main() {
	cin >> N >> K >> S;
 
	S[K - 1] += 'a' - 'A';
 
	cout << S << endl;
}

Last Stone Weight II [LeetCode 1049]

https://leetcode.com/contest/weekly-contest-137/problems/last-stone-weight-ii/

N個の石があり、それぞれの重さがわかっている。
2つの石を選んでぶつけるという操作をできなくなるまで行う。
ぶつけると、

  • 同じ重さであれば、2つとも消滅
  • 差があれば、差分の石が残る

という結果になる。
最終的に残る石の重さとして最小のものを答えよ。
(残らなければ0を答える)

1≦N≦30
1≦重さ≦1000

前提知識

解説

https://leetcode.com/contest/weekly-contest-137/submissions/detail/229837009/

今回の問題はある問題に帰着できる。
石を2グループに分けたときにそれぞれのグループの総和の差が最終的に残る石の重さになる。
よって、石を2グループに分けたときにそれぞれのグループの総和の差を最小化すればいい。
自分はもちろん未証明。
 
あとは、これをどう実現するかであるが、制約を見ると、半分全列挙が使えそうだ。
2グループで作れる総和を計算する。
グループ0で総和aを作れたとする。ここからグループ1から総和bを最適に取ってくることを考えると、
全体をtotとすると、a + b = tot/2になるべく近いほうがいい。
よって、b = tot/2-a付近の数が答えになりうるということ。
よって、グループ0で作れる総和aは全探索することにして、
グループ1での総和は二分探索をしてtot/2-a付近の数だけ検証する。
イメージし辛いなら、三分探索をしても大丈夫だ。

class Solution {
public:
	pair<set<int>, int> f(vector<int> v) {
		int n = v.size();
		set<int> s;
		rep(msk, 0, 1 << n) {
			int tot = 0;
			rep(i, 0, n) if (msk & (1 << i)) tot += v[i];
			s.insert(tot);
		}
		int sm = 0;
		rep(i, 0, n) sm += v[i];
		return { s, sm };
	}
	int lastStoneWeightII(vector<int>& stones) {
		int n = stones.size();

		vector<int> v[2];
		rep(i, 0, n) v[i % 2].push_back(stones[i]);

		auto p0 = f(v[0]);
		auto p1 = f(v[1]);
		int tot = p0.second + p1.second;

		int ans = inf;
		fore(x, p0.first) {
			int a = x;

			int opt = tot / 2 - a;
			auto optite = p1.first.lower_bound(opt);

			auto ite = optite;
			ite--;
			rep(i, 0, 5) {
				int b = *ite;
				
				int sm1 = a + b;
				int sm2 = tot - sm1;
				int d = abs(sm1 - sm2);
				chmin(ans, d);
				if (ite == p1.first.begin()) break;
				ite--;
			}

			ite = optite;
			rep(i, 0, 5) {
				if (ite == p1.first.end()) break;

				int b = *ite;

				int sm1 = a + b;
				int sm2 = tot - sm1;
				int d = abs(sm1 - sm2);
				chmin(ans, d);
				ite++;
			}
		}

		return ans;
	}
};

Longest String Chain [LeetCode 1048]

https://leetcode.com/contest/weekly-contest-137/problems/longest-string-chain/

N個の文字列がある。
文字列Aのどこかにちょうど1文字加えることで文字列Bになる → AはBのpredecessorと言う。
N個の文字列から何個か取って並べるとする。
それが、S1, S2, ..., SNであるとすると、S1はS2のpredecessor, S2はS3のpredecessor, ...という感じに
全てpredecessorの関係になっている列の最長は?

1 ≦ N ≦ 1000
1 ≦ 文字列長 ≦ 16

解説

https://leetcode.com/contest/weekly-contest-137/submissions/detail/229839298/

今回の問題は有向グラフに帰着することができる。
ある文字列Aがある文字列Bのpredessorであるとき、A -> Bと辺を張ることにする。
こうすると、できあがる有向グラフはDAGの形になっている。
DAGで最長パスを求めるときは、トポロジカルソートをしてDPという相場が決まっているのでやる。
dp[cu] := パスの末尾が頂点cuであるパスの最長

class Solution {
public:
	int longestStrChain(vector<string>& A) {
		int n = A.size();

		TopologicalSort ts(n);
		rep(a, 0, n) rep(b, 0, n) if (A[a].size() + 1 == A[b].size()) {
			int aa = 0;
			rep(bb, 0, A[b].size()) {
				if (aa == A[a].size()) break;
				if (A[a][aa] == A[b][bb]) aa++;
			}
			if (aa == A[a].size()) ts.add_edge(a, b);
		}

		vector<int> ord;
		ts.sort(ord);

		vector<int> dp(n, 1);

		fore(cu, ord) fore(to, ts.E[cu]) chmax(dp[to], dp[cu] + 1);
		int ans = 0;
		rep(i, 0, n) chmax(ans, dp[i]);
		return ans;
	}
};