2019-11-27

CODE FESTIVAL 2017 qualB C 3 Steps

俺ガイルとゲーマーズの最終巻が読めていないえぬわいです。今週は、全然解けてないですね〜。もっと解かないとな〜。

続きです。

ワカンねぇな〜って思って、解説見たら問題の解釈が間違っていたみたい。

思い出した2部グラフの特徴として、 * 同じ色同士への移動は、偶数長でできる。逆に、違う色同士では、奇数でできる。 * 完全2部グラフの辺数は、(同じ色の頂点数)*(違う色の頂点数)。これは、図を描けば明らか。 * 2 部グラフでないグラフは、奇サイクルを含んでいる。これは、前述した通り、同じ色は、偶数になるから。

ここらへんはちゃんと使えるようにならないと解けないような問題だった。解説は、結構わかった。

解説見て実装。

import sys

sys.setrecursionlimit(100000)
from collections import defaultdict

G = defaultdict(list)


N, M = map(int, input().split())
visited = [[False for i in range(N)] for j in range(5)]
for i in range(M):
    v,u = map(int, input().split())
    G[v-1].append(u-1)
    G[u-1].append(v-1)

# 頂点間に奇数長のパスがあるかどうか確認するために 2部グラフ 判定をする
COLOR = [0 for i in range(N)]

def dfs(pos, color):
    global COLOR
    COLOR[pos] = color
    ans = True
    for to in G[pos]:
        if COLOR[to] == color:
            return False
        elif COLOR[to] == 0:
            ans &= dfs(to, -color)
    return ans

if dfs(0, 1):
    count = 0
    for i in COLOR:
        if i == -1:
            count += 1
    another = N-count
    print(count*another-M)
else:
    # 2 部グラフではなかったので、完全グラフから M を引いた値を出力する
    print(N*(N-1)//2-M)

2019-11-21

AtCoder ABC 126 D - Even Relation

競技プログラミング

ぼくがかんがえたさいきょうの生活習慣を送っているえぬわいです。3 日だけですけど。これから続けていくんだという気持ち。

qiita.com

続きです。

atcoder.jp

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)

2019-11-20

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|)となるらしい。ふむ。俺もふわふわのクッションが足りないのかもしれない。ふむ。

2019-11-19

ABC 087 D People on a Line

競技プログラミング

ストライク・ザ・ブラッドで好きなキャラクターは藍羽浅葱。えぬわいです。

qiita.com

続き。

atcoder.jp

重み付きUnionFind木というのがあるらしい... ノード間の重みを保存しつつ、縮約していくアルゴリズムらしい。

qiita.com

けんちょんさんの記事を参考にして、理解してみる。ベースは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')

2019-11-15

ARC 036 D 偶数メートル

競技プログラミング

qiita.com

続き。

atcoder.jp

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で判断できる。短すぎるだろ...

覚えておきたいテクニックだと思いました。

2019-11-11

ARC 097 D Equals

競技プログラミング

ポスター発表が終わりました。えぬわいです。

qiita.com

続きです。

atcoder.jp

概要

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)

通った！！！！

2019-11-09

ABC 049 D 連結

競技プログラミング

qiita.com

続きです。

atcoder.jp

考察まとめです。

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 次元ぽくすると、上記の計算量を落とした解答にありつける。

いろんなことで四苦Hack（仮）

b1u3の技術ブログ

CODE FESTIVAL 2017 qualB C 3 Steps

AtCoder ABC 126 D - Even Relation

2部グラフ判定

ABC 087 D People on a Line

ARC 036 D 偶数メートル

ARC 097 D Equals

概要

考えたこと

ABC 049 D 連結