2018-12-06

最小全域木

この記事は
https://adventar.org/calendars/3598
の6日目の記事として書かれました。
昨日の記事はsatosさんの独断と偏見による根津/本郷飯事情でした。

19erのomochana2というものです。
最小全域木を扱う際で有効な定理を紹介したいと思います。めっちゃ数学っぽい話になって申し訳ないです。結果だけ知りたかったら四角で囲ってある部分をサーっと読んでください。一番下に定理を使って解ける演習問題も置いといたので、よかったら解いてください。

要は、辺が最小全域木に含まれたり含まれなかったりするための条件を考えようぜって話です。
カット特性

辺のコストが全て異なるとする。 $S$ は空集合でも $V$ 全体でもない点の部分集合であるとし、辺 $e=(v,w)$ は端点の一方が $S$ に他方が $V-S$ に属する辺のうちでコストが最小のものであるとする。すると、どの最小全域木も辺 $e$ を含む。

図にするとこうなっています。
ここで辺 $e$ のコストは $e',f$ よりも小さいです。

軽く証明します。 $e$ が最小全域木に含まれていないとします。すると、 $e'$ のような、 $S$ と $V-S$ にまたがり、かつ $v$ から $w$ へのパス上(図でオレンジ色で示してあります)にある辺が存在します。 $e'$ を削除して、 $e$ を追加しましょう。すると新しいグラフも全域木となり、元の全域木よりもコストが下がりました。これは仮定と矛盾するので証明完了です。
簡単に言えば $e$ と、ある $S$ と $V-S$ にまたがる辺を交換しているわけですが、またがってさえすればどんな辺でもいいわけではないことです。実際 $e$ と $f$ を交換してしまうと、閉路ができてしまい、全域木ではなくなってしまいます。

この定理を利用するとKruskal法やPrim法の正当性が出来ますが、ここでは割愛します。

閉路特性

辺のコストは全て異なるとする。 $C$ を $G$ の任意の閉路とし、 $C$ に属する辺で最もコストの大きい辺を $e$ とする。このとき $e$ はGのどの最小全域木にも属さない。

カット特性は最小全域木に含まれる辺の条件だったのに対し、閉路特性は最小全域木に含まれない辺の条件です。これもカット特性のように辺を交換することによって証明できるので考えてみてください。

カット特性と閉路特性の合わせ技
ここからがアツいです。上の2つの定理を使うとこんなことが言えます。

辺のコストは全て異なるとする。辺 $e=(v,w)$ について、 $e$ よりコストの小さい辺のみからなるパス $P$ で $v$ と $w$ を結ぶことができる $\Leftrightarrow$ $e$ は $G$ の最小全域木に含まれない。

証明.

$e$ よりコストの小さい辺のみからなるパス $P$ で $v$ と $w$ を結ぶことができる。 $\Rightarrow$ $e$ は $G$ の最小全域木に含まれない。
$e$ よりコストの小さい辺のみからなるパスで $v$ と $w$ を結ぶことができない。 $\Rightarrow$ $e$ は $G$ の最小全域木に含まれる。

この1,2が示されれば証明できたことになります。まず、 $P$ に $e$ を加えると $e$ がコスト最大であるような閉路が得られるため、閉路特性から $e$ は $G$ の最小全域木には含まれません。これで1は示されました。
逆に $v$ と $w$ は $e$ よりコストの小さい辺のみからなるパスで結ぶことができないとします。点の集合 $S$ を、 $e$ よりコストの小さな辺のみからなるパスで $v$ から到達可能な全ての点の集合とします。すると、仮定から $w \in V - S$ です。また、 $S$ の定義から、一方の端点xが $S$ に属し、他方yが $V-S$ に属して、eよりコストの小さい辺 $f$ は存在しません。もしそのような辺が存在したとすると、 $x$ は $e$ よりコストの小さい辺のみからなるパスで $v$ から到達可能であるので、 $y$ もまた到達可能になり、 $S$ の定義に属するからです。これによりカット特性を使えば、2も示されたので証明完了です。

コストが同じ辺がある場合
コストが全て異なるなら場合分けが、

$e$ よりコストの小さい辺のみからなるパス $P$ で $v$ と $w$ を結ぶことができる。
$e$ よりコストの小さい辺のみからなるパスで $v$ と $w$ を結ぶことができない。
の2つでよかったんですが、コストが同じ辺がある場合は、
$e$ 未満のコストの辺のみからなるパス $P$ で $v$ と $w$ を結ぶことができる。
$e$ 未満のコストの辺のみからなるパスで $v$ と $w$ を結ぶことは出来ないが、 $e$ 以下のコストの辺のみからなるパス $P'$ では $v$ と $w$ を結ぶことができる。
$e$ 以下のコストの辺のみからなるパスで $v$ と $w$ を結ぶことができない。

と3つになります。ここで1と3、2と5が対応していることに注意します。

実は3と5は1,2の証明をほぼそのまま適用できます。よって結果も同じです
問題は4ですが、もし $e$ が最小全域木に含まれていないとするなら、最小全域木上のパス $Q$ に $e$ とコストが同じ辺 $e'$ が存在します。もし $Q$ 上に $e$ よりも大きい辺 $f$ が存在するならば $e$ と $f$ を交換することによって、全域木のコストを下げることが出来てしまい矛盾します。よって $Q$ にはコストが $e$ 以下の辺しかないことになりますが、4の仮定により、 $e$ 未満のコストの辺のみからなるパスは存在しないため、全域木の全ての点が互いに到達可能であるという条件から $e'$ が存在します。よって $e$ と $e'$ を交換することによって、 $e$ を最小全域木に含めることができました。
$e$ が最小全域木に含まれているとすると、 $P'$ 上の $e$ とコストが同じで、最小全域木上にない辺 $e'$ が存在するので、これを $e$ と交換すれば $e$ を最小全域木から除外できました。

以上より、4が成り立つときは、全ての最小全域木には $e$ は含まれないが、 $e$ を含む最小全域木は存在する、となります。証明できたことをまとめると、

グラフ $G=(V,E)$ 上の辺 $e=(v,w)$ について、

$e$ 未満のコストの辺のみからなるパス $P$ で $v$ と $w$ を結ぶことができる。 $\Rightarrow$ $e$ を含む $G$ の最小全域木は存在しない。

$e$ 未満のコストの辺のみからなるパスで $v$ と $w$ を結ぶことは出来ないが、 $e$ 以下のコストの辺のみからなるパス $P'$ では $v$ と $w$ を結ぶことができる。 $\Rightarrow$ $e$ は $G$ の全ての最小全域木には含まれないが、 $e$ を含む $G$ の最小全域木は存在する。

$e$ 以下のコストの辺のみからなるパスで $v$ と $w$ を結ぶことができない。 $\Rightarrow$ $e$ は $G$ の全ての最小全域木に含まれる。

となります。これがおそらく一番使いやすい形になっています。

演習問題

連結グラフG(全ての点が互いに行き来可能)が与えられる。Gの特定の辺 $e$ が指定されるので $e$ を含むGの最小全域木が存在するかどうか $O(|V|+|E|)$ で判定せよ
最小全域木が複数あるかどうか判定せよ
"ほぼ木"が与えられる。このグラフは連結であり、 $|E|=|V|+8$ を満たす。この時最小全域木を $O(|V|)$ で与えよ
(難)(これも紹介したかった)最小全域木の辺 $|V|-1$ 本をコスト順に並び替えたものを $a$ とする。ある全域木の辺 $|V|-1$ 本をコスト順に並び替えたものを $b$ とした時、全ての $0 \leq i \leq |V|-2$ を満たす自然数 $i$ に対し、 $a_i \leq b_i$ を示せ(元ネタ:http://acm-icpc.aitea.net/index.php?plugin=attach&refer=2012%2FPractice%2F%E6%A8%A1%E6%93%AC%E5%9C%B0%E5%8C%BA%E4%BA%88%E9%81%B8%2F%E8%AC%9B%E8%A9%95&openfile=MedianTree.pdf)

参考文献

Jon Kleinberg, Eva Tardos(2008)「アルゴリズムデザイン」浅野孝夫, 浅野泰仁, 小野孝男, 平田富夫訳, 共立出版

明日の記事はlmt-swallowさんの"Browsing History Leakage (Sniffing?) について書きます"です。楽しみですね。

2018-12-04

SRM埋め(3)

SRM 714 easy
easyはこれくらいの難易度が良いよなぁ。何ターン目までに消さないといけないという条件が求まる。

SRM 713 easy
難しい。保留->わかったんですけど、easyにしては実装複雑すぎでは?と思ってkmjpさんの解説記事見たら全く同じでおったまげました。(p^d)^a=(p^e)^bみたいにpという一番簡単な形で累乗を表せばあとは適当にgcd取りながら計算していけばいいです。しかしこれがめんどくさい上に、工夫しないとO(n)になって死んでしまう。大変。

SRM 712 easy
良問。まず1ターン行動するとsumは2倍になることから何回行動するかはわかる。実験してみると2項係数がかかった式になるのでできる。Combinationをバグらせて遅かった。コード貼っときます。

ll C(int a, int b) {
	ll tmp = 1;
	rep(i, 0, b) {
		tmp *= (a - i);
		tmp /= (i + 1);
	}
	return tmp;
}

簡易版ですね。

SRM 711 easy
まずnがk桁１が連続するか見る。そうでなかったらk桁連続するところを1にしてそれ以降0にするのが最適。最初バグったコードを投げたけどなぜかsys test通った(えぇ…)

SRM 710 easy
できたんだけどこういう解法が怪しいやつは得意じゃない…。typeAとtypeBは可逆です。typeAのみでN-1に石を全部置けたらあとはtypeBでTに戻せばいいです。間隔的にはN-1以外のholeに作用させまくれば良さそうですが、実験してみるとそれでうまくいきそうなことがわかります。

SRM 709 easy
Aの要素が50以下なのでYのうち影響を及ぼすのは下6桁のみです。よってbitdpできます。

SRM 708 easy
constructive多すぎでは…similarityは減らしたくて、そうすると長さ1の文字列を並べるのが良いです。後はwxwxwx....みたいな文字列で帳尻合わせします。

SRM 707 easy
へびみたいにpathを蛇行させればいいです。実装まあまあ工夫できて結構早く通せた。

SRM 706 easy
混乱したのもあるけど無駄にdijkstra書いたせいで遅くなってしまった。ベルマンフォードは更新される数だけループする以外は、dijkstraの更新と同じことをちゃんと覚えておきましょう。あとtupleの使い方も覚えておきましょう。get < idx > (tuple)ですよ。

SRM 705 easy
グラフ張ってループあるか見るだけですがこういうめんどくさいのはSCCにやらせましょう。

SRM 704 easy
あまりバグらせることなくうまく出来たなぁと思ったけどみんな早すぎ。直径を最初に取ればいいです。よくあるやつ。

SRM 703 easy
あーこれtopcoder40問目のeasyだったのに誤読+全然思いつけなくてつらかった。sortして、前の方から順番に辺を張るみたいなことをすればいいです。

2018-11-30

SRM埋め(2)

当分easyで鍛えます。(気分でmedときます)

scoreですが目安としては
5分で満点*0.95
10分で満点*0.9
15分で満点*0.8
20分で満点*0.7
36分で満点*0.5
と覚えておけばよいでしょう。早解きは正義。

SRM 730 easy
「「「「「non decreasing」」」」コードは1発で書けたからもったいない。

SRM 729 easy
dpやるだけ

SRM 729 med
状態削減が本質になることに気づくのが遅すぎるし、角だけでいいと思って嘘解法してしまった。ダメダメ。辺全部試しましょう。

SRM 728 easy
結構好き。1つだけ見た時取りうる長さの候補がO( (logA)^2)通りだから、全部長さを試してminを取れば良い。
SRM 728 med
なんか昔に解いていた。座圧してdp

SRM 727 easy
難しい。後回し。->解きました。面白い。良問。SAがあったら直後にNを挿入して、後にTAを加えればいいです。なければ後にSANTAを加えればいいです。
SRM 727 med
真ん中の#の個数と.の個数を決め打つ

SRM 726 easy
条件整理して同じようなDPを3回する。

SRM 725 easy
bitDP復元

SRM 724 easy
まずorでbitが0の桁は2つの数もその桁は0です。1+0,1+1を判別するためにはt=sum-orを考えればいいです。ただし(t & or)==orを満たしている必要が有ります。(これを見逃した)桁ごとに条件が出たので、あとは簡単です。

SRM 723 easy
これはうまく出来た。上のbitから見ていって2つ以上そのbitを持つ数があれば、答えは(2^(k+1))-1みたいな形になります。
1つならその数をvとしてvを削除、v-2^kを追加して下の桁を見に行けばよいです。

SRM 722 easy
桁dpで良いです。でもdpの形にする必要はなかった。

SRM 720 easy
渾身の出来。だいぶ時間意識したら結構うまく実装できた。疲れるけど。
digit1とdigit2のそれぞれ1つの桁に注目して数え上げdpすればいいです。

SRM 719 easy
どっかの行に行って移動します。
SRM 719 med
根を含む部分木を選択して、その部分木上にない頂点を取る問題になります。割と速く通せたと思う。欲を言えば緩和にもう少し早く気づけたらよかった。

SRM 718 easy
渾身の出来。適当に0かけながらDPするだけ。

SRM 717 easy
フローからの復元と思って、それで通ったけどなんか想定解は違ったみたい。ちゃんと理解したい。

SRM 716 easy
A = sa + sb, B = sb + sc, C = sc + saみたいに対称な形にして、sa,sb,scのうち一番短いものを01010101...として、残りは000000....と111111....にするみたいな方針で通りました。

SRM 715 easy
いやどういうこと。今までtopcoderで解いた中で一番簡単だったかも。+の数と-の数大きい方が答えです。

2018-11-30

SRM埋め

最近のSRM無駄にconstructive多いっすね。

SRM 742 easy
1,0.5,0.25,0.125....と1,2,4,8,16....を作って適当に繋げれば良いけどバグった。
SRM 742 med
kmpチックにbitdpすればいい

SRM 740 easy
どういうことやねんと思ったら罠が有りました…
SRM 740 medium
dp復元久しぶりに書いてめちゃくちゃバグった。

SRM 739 easy
虚無実装だけど、こういうのはだいたい全探索できるからありがたい。
SRM 739 med
にぶたんしたあと適当に貪欲でいいなぁと思って実装したけど、条件を間違えまくって辛かった。
正しいのは、前の餌場から見ていって、空腹度が大きい牛を使っていくんですが、今の餌場では空腹を満たせない時、次の餌場でもそうであればfalseです。

(SRM 738は神回です)
SRM 738 easy
長さが整数である格子点上の2点がかなり少ないことを利用する。
SRM 738 med
実は独立に考えて良い。良問。

SRM 737 easy
面白い。全要素のxorをXとする。ある要素aをとって、X^aが0になる方法はたかだか1通り。
またX^a<=aという条件がつくが、これはXの最上位bitがaに含まれていることと同値。
よって奇数なら64, 65, 66...とかすればN<=37なので良くて、偶数なら全要素が上の条件を満たすのは不可能で、
1つ犠牲にすれば奇数と同じ状態になる。
SRM 737 med
は？0,1,-1に気をつけて掛け算するんですが、多倍長整数がいる。やめて。

SRM 735 easy
aaaaaa...とbbbbbb...を取ればたかだか2です。
SRM 735 med
条件はX(X-1)=0(mod m)です。XとX-1は互いに素なので、mの互いに素な積を全部試して、extgcdする。

SRM 734 easy
まず軸上は最初に除いておきます。そうすると、x>0,y>0,x^2+y^2<=r^2,gcd(x,y)=1なるx,yの個数を求めればよいです。
あとはx全部試してyは包除原理します。
SRM 734 med
ブラックジャックなんてしないで…

SRM 733 easy
ほんとうにやるだけ

SRM 732 easy
これ難しすぎるだろ…1点をひっくり返すのを繰り返すのが良いとわかりますが、領域が分かれている時もあるので注意。

SRM 731 easy
こういうの速くならないんだよね…dfsしていけばいいですが、文字列の扱いが若干複雑。

2018-11-25

Dwango Programming Contest V / 第5回ドワンゴからの挑戦状予選

DP Math

https://beta.atcoder.jp/contests/dwacon5th-prelims

アー

A
Nかけましょう。
B
なぜかバグらせた…上からbit決めましょう。
C
なんで思いつかなかったのかなぁ…ちゃんと順番決めて見ていかないからダメ。DとMの数もってしゃくとりすればいいです。

int N, Q;
string S;

void solve() {
	cin >> N;
	cin >> S;
	cin >> Q;
	while(Q--) {
		int k; cin >> k;
		ll res = 0;
		int D = 0, M = 0;
		ll cnt = 0;
		rep(i, 0, k) {
			if(S[i] == 'D') D++;
			if(S[i] == 'M') {
				M++;
				cnt += D;
			}
			if(S[i] == 'C') res += cnt;
		}
		rep(i, k, N) {
			if(S[i - k] == 'D') {
				D--; cnt -= M;
			}
			if(S[i - k] == 'M') M--;

			if(S[i] == 'D') D++;
			if(S[i] == 'M') {
				M++;
				cnt += D;
			}
			if(S[i] == 'C') res += cnt;
		}
		cout << res << "\n";
	}
}

D
わかったけどもっと速く詰められたよなぁ…値が3個だけというのはすぐ気づけたのに、累積和にすぐ言い換えられなかった…。
最大最小は和と交換可能、100回唱えます。
E
これもiteration回そうぜ…
問題自体はめちゃくちゃ面白いです。多項式の係数のgcdってこんな扱いできるのか。

int N;
ll A[MAX_N];

ll gcd(ll a, ll b) {
	return b == 0 ? a : gcd(b, a % b);
}

void solve() {
	cin >> N;
	rep(i, 0, N) cin >> A[i];
	sort(A, A + N);
	ll res = 1;
	rep(i, 0, N) MUL(res, gcd(A[i], i));
	cout << res << "\n";
}

C解けていれば赤パフォだったと思うと悔しすぎる。

自分で決めたルールをちゃんと守れていない感。

2018-11-22

DISCO presents ディスカバリーチャンネルコードコンテスト2017 予選

https://beta.atcoder.jp/contests/ddcc2017-qual/tasks

去年の予選です。ばちゃコンしました。

ABはい
C set
D
とりあえず、対称な4マスずつに分けて考えれば良いことがわかります。
すると縦に対称、横に対称、3マス塗られている、4マス塗られているの4パターンについて考えればよいです。
しかし最初に縦か横に対称性がある時、除かなくてはならないことに注意です。

int N, M;
int A, B;
string S[MAX_N];

void solve() {
	cin >> N >> M;
	cin >> A >> B;
	int V = 0, H = 0, D = 0, C = 0;
	bool odd = false;
	rep(i, 0, N) cin >> S[i];
	rep(i, 0, N / 2) {
		rep(j, 0, M / 2) {
			int cnt = 0;
			cnt += (S[i][j] == 'S');
			cnt += (S[i][M - 1 - j] == 'S');
			cnt += (S[N - 1 - i][j] == 'S');
			cnt += (S[N - 1 - i][M - 1 - j] == 'S');
			if(cnt == 4) D++;
			if(cnt == 3) {
				C++;
				odd = true;
			}
			if(cnt == 2) {
				if(S[i][j] == S[N - 1 - i][j] && S[i][M - 1 - j] == S[N - 1 - i][M - 1 - j]) V++;
				else if(S[i][j] == S[i][M - 1 - j] && S[N - 1 - i][j] == S[N - 1 - i][M - 1 - j]) H++;
				else odd = true;
			}
			if(cnt == 1) odd = true;
		}
	}
	if(odd || (V && H)) cout << max(A * (V + C), B * (H + C)) + (max(A, B) + A + B) * D + A + B << "\n";
	else {
		if(V) cout << max(A * (V + C - 1), B * (H + C)) + (max(A, B) + A + B) * D + A + B << "\n"; //C == 0
		else if(H) cout << max(A * (V + C), B * (H + C - 1)) + (max(A, B) + A + B) * D + A + B << "\n"; // C == 0
		else cout << max(A * (V + C), B * (H + C)) + (max(A, B) + A + B) * D << "\n"; //C == 0, V == 0, H == 0
	}
}

場合分けを詰めるタイプの問題苦手なんだよなぁ。

2018-11-21

「みんなのプロコン 2018」決勝B: 経路が色々

Constructive

https://beta.atcoder.jp/contests/yahoo-procon2018-final/tasks/yahoo_procon2018_final_b

たぶん想定解よりも思いつきやすい方法で。
base-3でやらず、base-2でやりました。例えばK=217(二進法で11011001)ならこのようにやります。

........#
.##.###.#
..#..##.#
.........
.......#.
.......#.
.....#.#.
.....#.#.
...#.#.#.
...#.#.#.
.#.#.#.#.
.........

ポイントは下の三角形の領域で2^Nを作り出していることです。
上の3行でうまくbitに対応するように制御している感じです。よく見ると3行目が..#..##.(#)となっており、1が.、0が#に対応していることがわかります。

ll K;
ll ans[64][61];

void solve() {
	cin >> K;
	for(int i = 1; i < 61; i += 2) {
		for(int j = 0; j < i; j++) ans[62 - j][i] = 1;
	}
	rep(i, 0, 3) ans[i][60] = 1;
	int pv = 0;
	rep(i, 0, 60) {
		if(!(K & (1ll << (59 - i)))) {
			ans[1][i] = 1;
			ans[2][i] = 1;
			pv = 0;
		}
		else {
			if(pv == 1) ans[1][i] = 1;
			pv = 1;
		}
	}
	cout << 64 << " " << 61 << "\n";
	rep(i, 0, 64) {
		string str;
		rep(j, 0, 61) str += (ans[i][j] ? '#' : '.');
		cout << str << "\n";
	}
}