AtCoder ABC 126 D - Even Relation
ぼくがかんがえたさいきょうの生活習慣を送っているえぬわいです。3 日だけですけど。これから続けていくんだという気持ち。
続きです。
ARC 036 D 偶数メートルのとっかかりの部分みたいな感じでした。たまたま偶数メートルの解説を読んだので、その知識を使ったら解法がすぐに見つかりました。
ポイントとしては、
- 重さは、偶数、奇数で、場合分けして、すべての辺を重さ 1 として、重さの概念をなくす。
- 塗ってみる
という感じです。
重さが偶数の辺が入った時は、間に無駄な頂点を追加して、その頂点を挟んで、重さ 1 の辺でつなぐことにする。重さが奇数の時は、そのまま、重さ 1 の辺にする。ここから 2 色で塗っていくと、すでに彩色されている。2部グラフの判定と多分同じ計算量だから、O(|E|+|V|)でO(2N)でO(N)になるのかな?
偶数になる理由として、頂点を増やした後のグラフについて、どの同じ色の頂点の組も間にある辺の数は常に偶数になっているからというのがあげられる。辺の重さは、1 としているから、辺の数=距離となる。
from collections import defaultdict import sys sys.setrecursionlimit(1000000) G = defaultdict(list) N = int(input()) C = [0 for i in range(N)] last = N def rec(pos, c): """ 2 色で塗ることができることが保証されている """ global C C[pos] = c for to in G[pos]: if C[to] == 0: rec(to, -c) for i in range(N-1): u, v, w = map(int, input().split()) u -= 1; v -= 1 # 無向グラフ if w%2 == 0: G[u].append(last) G[last].append(u) G[v].append(last) G[last].append(v) C.append(0) last += 1 else: G[u].append(v) G[v].append(u) rec(0, 1) for i in range(N): print(0 if C[i] == -1 else 1)
2部グラフ判定
アニマエールのOP・EDを聞いたら、見返す機運が高まってるえぬわいです。
今日は、蟻本に載ってる2部グラフ判定を自分で実装して理解しました。
ポイントとしては、
- とりあえず、塗っていって判定する
- 塗ってる最中でダメだと思ったら打ち切る
- 色は、符号を反転させたもので区別するとコードが減らせる
と言ったところかな。
pythonで書いたらこんな感じ
from collections import defaultdict G = defaultdict(list) # 色を保持するリスト。0 で初期化しておいて、訪れたことがあるかにも使う # 1, -1 のように反転させた符号にしておけば、-をつけただけでよくなる C = [] N, E = map(int, input().split()) for i in range(N): C.append(0) for i in range(E): fr, to = map(int, input().split()) G[fr].append(to) G[to].append(fr) def rec(pos, color): global C C[pos] = color for to in G[pos]: if C[to] == color: return False elif C[to] == 0 and not rec(to, -color): return False return True ans = True for i in range(N): if C[i] == 0: ans &= rec(i, 1) print(ans)
計算量は、辺と頂点を 1 度ずつ見ているので、O(|E|+|V|)
となるらしい。ふむ。俺もふわふわのクッションが足りないのかもしれない。ふむ。
ABC 087 D People on a Line
ストライク・ザ・ブラッドで好きなキャラクターは藍羽浅葱。えぬわいです。
続き。
重み付きUnionFind木というのがあるらしい... ノード間の重みを保存しつつ、縮約していくアルゴリズムらしい。
けんちょんさんの記事を参考にして、理解してみる。ベースはUnionFind。
ノードを結合する時、シンプルなUnionFindでは、そこまで、どっちをどっちにっていうのは意識しなくてよかったけど、これは、重みに向きがあるので、しっかり考えないといけない。
pythonで書き直して、問題を解いてみる。
class WeightedUnionFind(): def __init__(self, n): self.par = [i for i in range(n)] self.rank = [0 for i in range(n)] # 親ノードとの重み self.diff_weight = [0 for i in range(n)] def find(self, x): if self.par[x] == x: return x # 親ノードはまだ上書きしない root = self.find(self.par[x]) self.diff_weight[x] += self.diff_weight[self.par[x]] self.par[x] = root return self.par[x] def weight(self, x): """ x 根に対する重みを返す """ self.find(x) return self.diff_weight[x] def diff(self, x, y): """ x と y の差分をとる """ return self.weight(y) - self.weight(x) def unite(self, x, y, w): """ ノード x の下にノード y をつける。辺の重みは、w """ # ただし、実際には、x の根と y の 根をくっつけるので、補正 w += self.weight(x); w -= self.weight(y) x = self.find(x); y = self.find(y) if x == y: return if self.rank[x] < self.rank[y]: # y の下に x をつけることになるので、重さは反転させる self.par[x] = y w = -w self.diff_weight[x] = w elif self.rank[y] < self.rank[x]: self.par[y] = x self.diff_weight[y] = w else: self.par[y] = x self.rank[x] += 1 self.diff_weight[y] = w N, M = map(int, input().split()) wuf = WeightedUnionFind(N) for i in range(M): l, r, d = map(int, input().split()) l -= 1; r -= 1 # これまでに入力されたものと等しくないか確認する if wuf.find(l) == wuf.find(r): if wuf.diff(l, r) != d: print('No') break else: wuf.unite(l, r, d) else: print('Yes')
ARC 036 D 偶数メートル
続き。
ARC D だけあって解答の読み応えがちげぇぜ(解答見た)
UnionFindを使うと、状態管理をすることができる例。
UnionFindで N 個の頂点間を偶数距離で移動できるかの判定に使っている。解答みておったまげた。
class UnionFind(): def __init__(self, n): self.par = [i for i in range(n)] self.rank = [0 for i in range(n)] def find(self, x): if self.par[x] == x: return x self.par[x] = self.find(self.par[x]) return self.par[x] def unite(self, x, y): x = self.find(x); y = self.find(y) if x == y: return if self.rank[x] < self.rank[y]: self.par[x] = y elif self.rank[y] < self.rank[x]: self.par[y] = x else: self.rank[y] += 1 self.par[x] = y N, Q = map(int, input().split()) uf = UnionFind(2*N) for i in range(Q): w, x, y, z = map(int, input().split()) if w == 1: if z%2 == 0: # 青 uf.unite(2*(x-1), 2*(y-1)) # 赤 uf.unite(2*(x-1)+1, 2*(y-1)+1) else: uf.unite(2*(x-1), 2*(y-1)+1) uf.unite(2*(x-1)+1, 2*(y-1)) else: if uf.find(2*(x-1)+1) == uf.find(2*(y-1)+1): print('YES') else: print('NO')
問題の解答の一番最後に載ってた。 基本的に、2 部グラフから考察を重ねるのが、勉強しがいのあるやり方みたいだ。
同じ頂点番号の頂点を 2 つずつ用意して、青、赤に分けておく。もし、道路ができる時、距離が偶数なら、その同じ色同士を結ぶ。偶数じゃなかったら、別の色同士を結ぶ。最終的に、赤だけを見て、同じ連結成分なら、YES
, 違かったらNO
で判断できる。短すぎるだろ...
覚えておきたいテクニックだと思いました。
ARC 097 D Equals
ポスター発表が終わりました。えぬわいです。
続きです。
概要
1 から N までの数列をシャッフルする。ある数字の組みが与えられるので、その組みの位置をスワップして、最大何個まで元の位置に戻せるかという問題。
考えたこと
組みとして、(1, 2)と(2, 3)のような組みが与えられたとき、共通する数字があれば、与えられた数字の集合は、すべて入れ替えられる。これを、Union-Findで記録していく。p の i 番目の中身が、5 だったとき、それを p の 5 番目に移動させるには、5 が入っている位置と、p の 5 番目が同じ、グループに入っていれば良いので、蟻本の関数を使うと、same(p[i], i)
が Trueなら、p[i] = i という関係にすることができる。
以下、解答。
N, M = map(int, input().split()) p = list(map(int, input().split())) class UnionFind(): def __init__(self, n): self.par = [i for i in range(n)] self.rank = [0 for i in range(n)] def find(self, x): if self.par[x] == x: return x self.par[x] = self.find(self.par[x]) return self.par[x] def unite(self, x, y): x = self.find(x) y = self.find(y) if x == y: return if self.rank[x] < self.rank[y]: self.par[x] = y elif self.rank[y] < self.rank[x]: self.par[y] = x else: self.rank[y] += 1 self.par[x] = y uf = UnionFind(N) for i in range(M): x, y = map(int, input().split()) uf.unite(x-1, y-1) ans = 0 for i in range(N): if uf.find(p[i]-1) == uf.find(i): ans += 1 print(ans)
通った!!!!
ABC 049 D 連結
続きです。
考察まとめです。
Union-Find木を使って解いてみる。まずTLEになったやつ。
class UnionFind(): def __init__(self, n=None): if type(n) == int: self.par = [i for i in range(n)] self.rank = [0 for i in range(n)] else: self.par = [] self.rank = [] def init(self, n): self.par = [i for i in range(n)] self.rank = [0 for i in range(n)] def find(self, x): """ ノード x の根を求める """ if self.par[x] == x: return x self.par[x] = self.find(self.par[x]) return self.par[x] def unite(self, x, y): root_x = self.find(x); root_y = self.find(y) if root_x == root_y: return if self.rank[root_x] < self.rank[root_y]: self.par[root_x] = root_y elif self.rank[root_y] < self.rank[root_x]: self.par[root_y] = root_x else: self.par[root_y] = root_x self.rank[root_x] += 1 def same(self, x, y): return self.find(x) == self.find(y) N, K, L = map(int, input().split()) road = UnionFind(N) rail = UnionFind(N) for i in range(K): p, q = map(int, input().split()) road.unite(p-1, q-1) for j in range(L): r, s = map(int, input().split()) rail.unite(r-1, s-1) for i in range(N): for j in range(N): if road.find(i) == road.find(j) and rail.find(i) == rail.find(j): ans[i] += 1 for i in range(N): print(ans[i], end=' ') print('')
これは、結果的に
for i in range(N): for j in range(N): if road.find(i) == road.find(j) and rail.find(i) == rail.find(j): ans[i] += 1
この部分がまずかった。
これは、数え上げで、計算量を減らすことができるようだ。
for i in range(N): ans[(road.find(i), rail.find(i))] += 1 for i in range(N): print(ans[(road.find(i), rail.find(i))], end=' ') print('')
こんな感じに。
これは、各頂点が、少なくとも 1 つのグループに属しているので、根が同じものを数えれば、どれだけの頂点数があるのか数えることができるということを使用している。
つまり、
# 考察のため、キーを一次元にした for i in range(N): for j in range(N): if road.find(i) == road.find(j): ans[i] += 1
これは、
for i in range(N): ans[road.find(i)] += 1
とすることができる。
これを、2 次元ぽくすると、上記の計算量を落とした解答にありつける。
ATC 001 B Union Find
人間は愚か。えぬわいです。
Union-find木の講座用の問題らしい。
Union-Find木とは
- グループの併合と判定ができるアルゴリズム
- 併合するのは、グループ同士、判定できるのは、ノード。つまり、グループは木で表される。
初期化
はじめに N 個のノードを用意する。はじめは、辺はない。
併合
片方の木の根からもう片方の木の根に接続する。
判定
それぞれのノードの根を辿り、同じノードだと同じグループ。違かったら別のグループ。
木のランク
ここでは、木を構成する最大段数を意味する。
以下実装。
MAX_N = 100000 par = [0 for i in range(MAX_N)] # par[i] は、ノード i の親ノードの番号 rank = [0 for i in range(MAX_N)] # rank: ノード単体の時が 0 def init(n): global par, rank for i in range(n): par[i] = i # 親は自分自身 rank[i] = 0 # 単体のとき、rank は 0 # 判定: ノード x の根を求める def find(x): global par if par[x] == x: # 根のノードは自分自身が親 return x # return find(par[x]) この場合、縦に連なる場合で最悪ケースになるので改良する else: par[x] = find(par[x]) # 辿ったノードを根に付け替える return par[x] # 併合: ノード x と ノード y を同じグループにする。考えとしては、根を見つけてつなぐ。 def unite(x, y): global rank, par root_x = find(x) root_y = find(y) if root_x == root_y: # そもそも同じグループだった return if rank[root_x] < rank[root_y]: par[root_x] = root_y # ランクの大きい方の根に小さい方の木の根をつなぐ elif rank[root_y] < rank[root_x]: par[root_y] = root_x else: par[root_y] = x rank[root_x] += 1 # ランクが同じ時だけランクが増える def same(x, y): return find(x) == find(y) N, Q = map(int, input().split()) init(N) for i in range(Q): p, a, b = map(int, input().split()) if p == 0: unite(a, b) else: print('Yes' if same(a, b) else 'No')
前蟻本読んだ時より、すんなり入ってきた感じがする。理解深まった感がある。 あと、同じATCの問題に、フーリエ変換の問題があって面白そうだなと思った。(やってない)周波数特性求めるのにしか使ってないので、現実的な問題に即して使えるんだなぁという感じがした。あとでやりたい。