Codeforces Round #400 (Div. 1 + Div. 2, combined) ABCD

コンテストページのURLはこちらです。
Dashboard - ICM Technex 2017 and Codeforces Round #400 (Div. 1 + Div. 2, combined) - Codeforces

A. A Serial Killer

問題概要

2つの文字列 $S_1,S_2$ に対して、続く $n$ 個の以下のクエリ:
「 $S_1,S_2$ のうち、文字列 $s$ である方を文字列 $t$ で置き換える」
を処理するごとに、 $S_1,S_2$ を出力する問題です。
ただし、 $1\leq n \leq 10^3$ 、(各文字列長) $\leq 10$ です。

解法

ザ・やるだけ、な問題です。
問題に与えられた通り、実装していけば良いです。

コード(C++)

▶表示する

#include <iostream>
#include <string>

#define INIT std::ios::sync_with_stdio(false);std::cin.tie(0);
#define REP(i, n) for(int i=0;i<int(n);++i)

int main() {
	INIT;

	std::string S1, S2;
	std::cin >> S1 >> S2;
	int n;
	std::cin >> n;

	std::cout << S1 << " " << S2 << "\n";
	REP(i, n) {
		std::string s, t;
		std::cin >> s >> t;

		if (S1 == s) S1 = t;
		else         S2 = t;

		std::cout << S1 << " " << S2 << "\n";
	}
	return 0;
}

問題文そのままの実装です。

ひとこと

これは特に引っかかるポイントはありませんね。

B. Sherlock and his girlfriend

Problem - B - Codeforces

問題概要

ある $n$ に対して、 $2,3,\cdots ,n+1$ の数に次が成り立つよう色を塗ります。
「ある相異なる2つの数 $p,q$ について、 $p$ が $q$ の素因数になっている、つまり $p$ が素数かつ $q$ が $p$ で割り切れるとき、 $p$ と $q$ の色が同じになってはいけない」

このとき、使う色の最小数 $k$ とその色の塗り方を出力する問題です。
ただし、 $1\leq n \leq 10^5$ です。
なお、 $k$ が最小であり塗り方が条件を満たしていれば、どのような出力でも構いません。

解法

まず条件から、明らかに合成数(素数ではない数)同士は同じ色で塗ってよいことがわかります。
ある2つの数を同じ色で塗ってはいけないとき、そのどちらかは必ず素数となるためです。

そして、同様に素数同士も同じ色で塗ってよいことが分かります。
ある2つの数を同じ色で塗ってはいけないとき、それら2数が両方素数だと、一方でもう一方は割ることが出来ないためです。

よって、素数と合成数をそれぞれ違う色で塗ればよいことが分かりました。

だからといって $k$ は常に $2$ であるかというと、そうではありません。
$n=1$ のとき、塗られる数は $\mathtt{2}$ のみであり、
$n=2$ のとき、塗られる数は $\mathtt{2,3}$ の2つとなります。

これらは、全て同じ色で塗っても良いため、 $k=1$ となります。

なお、 $n=3$ より大きい数では、 $\mathtt{2}$ と $\mathtt{4}$ とが塗られる数に現れるため、 $k=2$ となります。
（ $\mathtt{2}$ は素数であり、 $\mathtt{4}$ は $\mathtt{2}$ で割り切れます）

コード(C++)

▶表示する

#include <iostream>

#define INIT std::ios::sync_with_stdio(false);std::cin.tie(0);
#define FOR(i, a, b) for(int i=(a);i<(b);++i)

bool isPrime(int n) {
	if (n < 2) return false;
	for (int i = 2; i * i <= n; ++i) {
		if (n % i == 0) return false;
	}
	return true;
}

int main() {
	INIT;

	int n;
	std::cin >> n;

	if (n == 1) {
		std::cout << 1 << "\n";
		std::cout << 1 << "\n";
		return 0;
	}
	if (n == 2) {
		std::cout << 1 << "\n";
		std::cout << "1 1" << "\n";
		return 0;
	}

	std::cout << 2 << "\n";
	FOR(i, 2, n + 1 + 1) {
		if (isPrime(i)) std::cout << 1;
		else            std::cout << 2;

		std::cout << " ";
	}
	std::cout << "\n";
	return 0;
}

頭の方にある関数 $\mathtt{isPrime}$ は、その名の通り「与えられた引数 $\mathtt{n}$ が素数であるかを判断する」関数です。
$2$ から $\sqrt{n}$ まで割りきれるか否かを調べてあげることで素数かどうかを判定することが出来ます。

なお、この場合は計算量は $O(n\sqrt{n})$ となりますが、 $n$ の制約は $1\leq n \leq 10^5$ であるため問題ないです。
（実際は、正整数 $m$ の倍数が $\lfloor \frac{n}{m} \rfloor$ 個あるため素数判定がすぐ終わる数もあり、もっと計算量は小さくなります）

エラトステネスの篩を用いてあらかじめ $n$ 以下の素数リストを作っておくことで $O(n)$ で解くことも出来ます。

ひとこと

コンテスト中は、問題の示す通り各数に対して素因数であり同じ色であるものの色を変えていく、という実装にしていました
→コレ

しかし、このやり方でもそこまで計算量が大きくならなかったため、46ms程度で通りました。

あと、素因数ではなく因数でやってWAを貰っていた人が結構多かったみたいです。
（私も1WA頂きました）

C. Molly's Chemicals

Problem - C - Codeforces

問題概要

整数 $n,k$ と、数列 $a_1, a_2, \cdots, a_n$ が与えられます。
このとき、区間 $[a_l, a_r](l\leq r)$ に含まれる項の和が $k$ の非負整数乗となるような区間が何通りあるか、を答える問題です。
ただし、 $1\leq n\leq 10^5, 1\leq |k|\leq 10, -10^9\leq a_i\leq 10^9$ です。

（ $k$ の非負整数乗とは、 $k^0, k^1, k^2, \cdots$ を指します）

解法

まずすぐに思いつくのは、全ての区間 $[a_l, a_r](l\leq r)$ に対して和を求め、それが $k$ の非負整数乗となっているかを調べる方法です。

しかし、これでは区間の列挙に $O(n^2)$ 時間がかかってしまいます。

そこで、今回はあくまで条件を満たす区間の個数だけが分かればよいため、「累積和をmapでカウントする」という手法を取ります。

まず、 $a_i$ の累積和 $s_i$ を取ります。ここで、便宜上 $s_0 = 0$ としておきます。
$\displaystyle s_i = \sum^i_{j=1}a_j$

そして、この $s_i$ の値を、番号が大きい順にmapでカウントしつつ、差が $k^p$ ( $p$ は非負整数)であるものの数を数えていきます。

この方法で、全ての条件を満たす区間を調べ上げることが出来ます。

実際に、具体例を見てみるとわかりやすいでしょう。

今、 $n=4, k=-3, a=\{3, -6, -3, 12\}$ とします（これは問題でも与えられたサンプル2と同じものです）。

まず、累積和を取ると、 $s=\{0,3,-3,-6,6\}$ となります。

次にこの累積和をmapでカウントしていきますが、これは横軸 $i$ 、縦軸 $s_i$ の折れ線グラフを考えるとわかりやすいでしょう。
以下のスライドでこの具体例について述べているので、参照してください。

累積和をmapに入れて区間の和をカウントする from satanic

上記スライドでは、分かりやすいようにカウントしていない部分に $0$ を入れておきましたが、実際に $0$ を入れない方がいいです。
これは、mapへのアクセスに掛かる計算量が要素数の対数時間となっているためです。

アクセス時間が延びるのに何故mapを使うかについて簡単に説明します。
累積和の値は最小で $10^{-14}$ 、最大で $10^{14}$ ほどになります。
これほど大きな区間を配列で管理することは出来ません。メモリ制限に引っかかってしまいます。

そこで、累積和の個数は $n+1$ 個しか取らないため、これらを全てmapに入れたとしてもアクセスには $O(\log n)$ 時間しかかかりません。

また、 $k^p$ ( $p$ は非負整数)について、 $p$ はいくらまで取ればよいかですが、
累積和 $s_i$ は高々 $10^{14}$ くらいの数をとります。
そのため、 $|k|>1$ のとき、 $2^p < 10^{14}$ より $p<46.5\cdots$ となるため、 $p=50$ くらいまで調べれば十分です。

今、 $|k|=1$ の時については考えませんでしたが、このとき、 $k$ を何乗してもその絶対値は変わりません。
具体的には、 $k=1$ の時は $1$ のみ、 $k=-1$ の時は $-1$ と $1$ のみの値しか取りません。

そのため、 $|k|=1$ の時をコーナーケースとして別に処理してやると良いでしょう。

コード(C++)

▶表示する

#include <iostream>
#include <vector>
#include <map>

#define INIT std::ios::sync_with_stdio(false);std::cin.tie(0);
#define REP(i, n) for(int i=0;i<int(n);++i)
#define RREP(i, n) for(int i=(n)-1;i>=0;--i)

using ll = long long;

signed main() {
	INIT;

	int n, k;
	std::cin >> n >> k;
	
	std::vector<int> a(n);
	REP(i, n) {
		std::cin >> a[i];
	}

	std::vector<ll> c(n + 1, 0);
	REP(i, n) {
		c[i + 1] = c[i] + a[i];
	}

	std::map<ll, int> map;
	ll ans = 0;
	int loop = 50;
	if (k ==  1) loop = 1;
	if (k == -1) loop = 2;

	RREP(i, n + 1) {
		ll kPow = 1;
		++map[c[i]];
		REP(j, loop) {
			if (std::abs(kPow) > 1e14) break;
			if (map.find(c[i] + kPow) != map.end()) {
				ans += map[c[i] + kPow];
			}
			kPow *= k;
		}
	}

	std::cout << ans << "\n";
	return 0;
}

まず、

std::vector<ll> c(n + 1, 0);
REP(i, n) {
	c[i + 1] = c[i] + a[i];
}

この部分では配列 $\mathtt{a}$ の累積和を配列 $\mathtt{c}$ に入れています。
なお、大きさを $\mathtt{a}$ よりも $1$ 大きくしているのは、頭に $0$ を入れることにより処理を簡単にするためです。

続いて、

int loop = 60;
if (k ==  1) loop = 1;
if (k == -1) loop = 2;

変数 $\mathtt{loop}$ は $k$ の指数部を最大どこまで調べればよいかを表します。
$k=1$ および $k=-1$ の時にループ回数を減らしているのは上に述べた通りです。

最後に、

RREP(i, n + 1) {
	ll kPow = 1;
	++map[c[i]];
	REP(j, loop) {
		if (std::abs(kPow) > 1e14) break;
		if (map.find(c[i] + kPow) != map.end()) {
			ans += map[c[i] + kPow];
		}
		kPow *= k;
	}
}

この部分で、スライドで説明した部分を実際に計算しています。
ここで、 $\mathtt{kPow}$ は $k$ の $p$ 乗を実際に計算した値を入れています。

$\mathtt{kPow}$ を計算する際に、ループの中で、

kPow *= k;

としていますが、これは標準の $\mathtt{std::pow}$ 関数が返り値に $\mathtt{int}$ 型を取るよう実装されていないためです。

また、

if (map.find(c[i] + kPow) != map.end()) {
	ans += map[c[i] + kPow];
}

ここでは調べる値がmapにカウントされているかを調べた上で、その値を答えに加算しています。

わざわざ調べているのは、mapに $\mathtt{operator[]}$ でアクセスを行うと、キーが指す要素が無い時、勝手にその要素を作ってしまうためです。（参考）
（上で述べたようにアクセスには要素数の対数時間かかるため、アクセスがどんどん遅くなっていってしまいます(参考)）

ひとこと

この問題はコンテスト中に解くことが出来ませんでした。
この「累積和をmapで管理する」というテクに名前等はついているんですかね？

D. The Door Problem

Problem - D - Codeforces

問題概要

ドアの数 $n$ 、スイッチの数 $m$ 、各ドアの初期状態 $\{r_1, r_2, \cdots, r_n\}(0:$ 鍵が開いている $,1:$ 鍵が閉まっている $,$ の $2$ 値を取る $)$ 、
各スイッチに繋がれたドアの数 $\{x_1, x_2, \cdots, x_m\}$ 、および各スイッチについて繋がれたドアの番号 $\{d_0, d_1, \cdots, d_{x_i-1}\}$ が与えられます。

あるスイッチをONにすると、そのスイッチに繋がれたドアの状態が全て逆になります（すなわち、開いているドアは閉まり、閉まっているドアは開きます）。
このとき、スイッチを適切に選択することで全ての鍵が同時に開いている状態にすることが出来るかを答える問題です。

ただし、
$2\leq n\leq 10^5, 2\leq m\leq 10^5, 0\leq r_i\leq 1, 0\leq x_i \leq n, 1 \leq d_i \leq n$
であり、ドアには丁度2つのスイッチが繋がっていることが保証されます。

解法

まず初めに、押すスイッチについての簡単な性質を挙げておきます。

スイッチを押す順は関係ない
同じスイッチは2回以上押す必要はない

このことからすぐに思いつく解法としては、全てのスイッチを押す/押さないで全探索するものがあります。
しかし、これでは計算量が $O(2^m)$ となり、とても間に合いません。

ここで、制約にある「ドアには丁度2つのスイッチが繋がっている」というものに注目すると、次のことが成り立ちます。

閉じているドアに対して繋がっている2つのスイッチは、どちらか1つだけ押す必要がある
開いているドアに対して繋がっている2つのスイッチは、両方押すか、両方押さないかのどちらかである必要がある

このことから、「あるスイッチの状態を決めると、そのスイッチが繋がるドアを介して別のスイッチの状態が決まる」ということが分かります。

この手の問題は、充足可能性問題(satisfiability problem, SAT)と呼ばれ、一般にはNP完全です。
しかし、この問題のように「状態を決めるものが(高々)2個しかない」という場合、2-SATと呼ばれ、関係式全体の大きさの線形時間で解くことが出来ます。
さらにこの問題では、2-SATの特殊な場合としてより簡単に考えることが出来ます。

詳しくは、以下のスライドを参照してください。
（一般の2-SATとの違いは最後の方にあります）

(ブログ用)Codeforces #400 D. The Door Problem from satanic

コード(C++)

▶表示する

#include <iostream>
#include <vector>

#define INIT std::ios::sync_with_stdio(false);std::cin.tie(0);
#define REP(i, n) for(int i=0;i<int(n);++i)

//Union-Find
class UnionFind {
private:
	std::vector<int> parent;
	std::vector<int> height;
	std::vector<int> m_size;

public:
	UnionFind(int size_) : parent(size_), height(size_, 0), m_size(size_, 1) {
		REP(i, size_) {
			parent[i] = i;
		}
	}
	void init(int size_) {
		parent.resize(size_);
		height.resize(size_, 0);
		m_size.resize(size_, 0);
		REP(i, size_) {
			parent[i] = i;
		}
	}
	int find(int x) {
		if (parent[x] == x) {
			return x;
		}
		return parent[x] = find(parent[x]);
	}
	void unite(int x, int y) {
		x = find(x);
		y = find(y);
		if (x == y) return;
		int t = size(x) + size(y);
		m_size[x] = m_size[y] = t;
		if (height[x] < height[y]) parent[x] = y;
		else parent[y] = x;
		if (height[x] == height[y]) ++height[x];
	}
	bool same(int x, int y) {
		return find(x) == find(y);
	}
	int size(int x) {
		if (parent[x] == x) {
			return m_size[x];
		}
		return size(parent[x] = find(parent[x]));
	}
};

signed main() {
	INIT;

	int n, m;
	std::cin >> n >> m;

	std::vector<int> r(n);
	REP(i, n) {
		std::cin >> r[i];
	}

	std::vector<std::vector<int>> d(m);
	REP(i, m) {
		int x;
		std::cin >> x;
		REP(j, x) {
			int d_input;
			std::cin >> d_input;
			d[i].emplace_back(d_input);
		}
	}

	std::vector<std::vector<int>> swch(n);
	REP(i, m) REP(j, d[i].size()) {
		swch[d[i][j] - 1].emplace_back(i);
	}

	UnionFind uf(m * 2);
	REP(i, n) {
		if (r[i] == 1) {
			uf.unite(swch[i][0]    , swch[i][1]    );
			uf.unite(swch[i][0] + m, swch[i][1] + m);
		}
		else {
			uf.unite(swch[i][0]    , swch[i][1] + m);
			uf.unite(swch[i][0] + m, swch[i][1]    );
		}
	}

	REP(i, m) {
		if (uf.same(i, i + m)) {
			std::cout << "NO\n";
			return 0;
		}
	}
	std::cout << "YES\n";
	return 0;
}

前半は素集合森の定義です。ここでの説明は省略します。

std::vector<std::vector<int>> swch(n);
REP(i, m) REP(j, d[i].size()) {
	swch[d[i][j] - 1].emplace_back(i);
}

ここでの $\mathtt{swch}$ は、各ドアが繋がるスイッチ2つを指す配列です。

UnionFind uf(m * 2);
REP(i, n) {
	if (r[i] == 1) {
		uf.unite(swch[i][0]    , swch[i][1]    );
		uf.unite(swch[i][0] + m, swch[i][1] + m);
	}
	else {
		uf.unite(swch[i][0]    , swch[i][1] + m);
		uf.unite(swch[i][0] + m, swch[i][1]    );
	}
}

この部分では、実際に問題を解くためのグラフを構築しています。

ここで、グラフ上での頂点番号について、「スイッチ $\mathtt{i}$ がオフである」という頂点の番号は $\mathtt{i+m}$ とするようにしています。
f:id:satanic0258:20170301233503p:plain
図は $m=3$ であるときですが、こうするとどのスイッチに対しても、オンとオフで頂点番号の差がちょうど $m=3$ となっていることが分かりますね。

頂点の繋げ方は、上に述べた通りです。

REP(i, m) {
	if (uf.same(i, i + m)) {
		std::cout << "NO\n";
		return 0;
	}
}
std::cout << "YES\n";
return 0;

最後に、あるスイッチ $\mathtt{i}$ がオンである状態とオフである状態が同じ連結成分に属していないかを調べます。

一つでも属していることが分かれば、条件を満たす組み合わせが存在しないため、答えは $\mathtt{NO}$ となります。
全て別の連結成分に属していれば、答えは $\mathtt{YES}$ となります。

ひとこと

2-SATについては、この問題に出会う数日前にF: Flags - AtCoder Regular Contest 069 | AtCoderを見て初めて知りましたが、コンテスト中に解くことが出来ました。
AtCoder様様ですね。

最後に

以上でABCD問題の解説を終わります。
EFG問題は別の記事に分けましたので、そちらを参照してください。
（まだ書き上げていないので少々お待ちください…）

sataniC++

C++、競プロ、数学などについて色々考えたりします。

Codeforces Round #400 (Div. 1 + Div. 2, combined) ABCD

A. A Serial Killer

問題概要

解法

コード(C++)

ひとこと

B. Sherlock and his girlfriend

問題概要

解法

コード(C++)

ひとこと

C. Molly's Chemicals

問題概要

解法

コード(C++)

ひとこと

D. The Door Problem

問題概要

解法

コード(C++)

ひとこと

最後に