BETA

今日の精進(20200107)

投稿日:2020-01-07
最終更新:2020-01-07

バイト始めだったわけだがすごい疲れた。働くって大変…

引っ越しできるかな?

縦横高さがC個分だけ入力されるので、1個の荷物の値をソートして、各荷物のn番目に大きい長さをC個分比べて、一番大きいものを取る。出力はそれらの積。

# coding: utf-8  
C = int(input())  
ans = [0, 0, 0]  
for i in range(C):  
    tmp = list(map(int, input().split()))  
    tmp.sort()  
    for j in range(len(ans)):  
        ans[j] = max(ans[j], tmp[j])  
print(ans[0] * ans[1] * ans[2])  

Union Find

UnionFind知らなかったので。しかしただUFをコピペするだけで終わってしまった…。

#coding: utf-8  

class UnionFind():  
    def __init__(self, n):  
        self.n = n  
        self.parents = [-1] * n  

    def find(self, x):  
        # xの根を探索  
        if self.parents[x] < 0:  
            return x  
        else:  
            # 再帰的に根を探索して経路圧縮  
            self.parents[x] = self.find(self.parents[x])  
            return self.parents[x]  

    def union(self, x, y):  
        # 2つの木をマージする。  
        x = self.find(x)  
        y = self.find(y)  
        if x == y:  
            return  

        if self.parents[x] > self.parents[y]:  
            x, y = y, x  

        self.parents[x] += self.parents[y]  
        self.parents[y] = x  

    def size(self, x):  
        # xの根の所属するグループの要素数を返す  
        return -self.parents[self.find(x)]  

    def are_same(self, x, y):  
        # 2つの要素の根が同じかどうかを調べる  
        return self.find(x) == self.find(y)  

    def members(self, x):  
        # xと同じ根の要素をリストで出力  
        root = self.find(x)  
        return [i for i in range(self.n) if self.find(i) == self.n]  

    def roots(self):  
        # 根である要素をリストで出力  
        return [i for i, x in enumerate(self.parents) if x < 0]  

    def group_count(self):  
        return len(self.roots())  

    def all_group_members(self):  
        return {r: self.members(r) for r in self.roots()}  

    def __str__(self):  
        return "\n".join("{} {}".format(r, self.members(r)) for r in self.roots())  

N, Q = map(int, input().split())  
uf = UnionFind(N)  
for i in range(Q):  
    p, a, b = map(int, input().split())  
    if p == 0:  
        uf.union(a, b)  
    else:  
        print("Yes" if uf.are_same(a, b) else "No")  

Decayed Bridges

むずい…。
入力された順番で答えを出すのは難しいので(どこに橋がかかっているかわからない)、はじめすべての島が独立で、後ろから順に橋をかけていけばいいというところまではできたが、そこまでだった。
UnionFindでやっていく。すべての島が連結でない時、不便度は$\frac{N*(N-1)}{2}$である。aとbがそもそも連結されている場合は不便度は変わらず、連結されていなければ一個前の不便度からaとbの所属するグループの分だけ不便度が解消されるので、ans[-1] - uf.size(a) * uf.size(b)となる。difficultyも水色だったし、やはり上位に行くにはこの手の有名アルゴリズムを覚えなければだめだと痛感した。

#coding: utf-8  

class UnionFind():  
    def __init__(self, n):  
        self.n = n  
        self.parents = [-1] * n  

    def find(self, x):  
        # xの根を探索  
        if self.parents[x] < 0:  
            return x  
        else:  
            # 再帰的に根を探索して経路圧縮  
            self.parents[x] = self.find(self.parents[x])  
            return self.parents[x]  

    def union(self, x, y):  
        # 2つの木をマージする。  
        x = self.find(x)  
        y = self.find(y)  
        if x == y:  
            return  

        if self.parents[x] > self.parents[y]:  
            x, y = y, x  

        self.parents[x] += self.parents[y]  
        self.parents[y] = x  

    def size(self, x):  
        # xの根の所属するグループの要素数を返す  
        return -self.parents[self.find(x)]  

    def are_same(self, x, y):  
        # 2つの要素の根が同じかどうかを調べる  
        return self.find(x) == self.find(y)  

    def members(self, x):  
        # xと同じ根の要素をリストで出力  
        root = self.find(x)  
        return [i for i in range(self.n) if self.find(i) == self.n]  

    def roots(self):  
        # 根である要素をリストで出力  
        return [i for i, x in enumerate(self.parents) if x < 0]  

    def group_count(self):  
        return len(self.roots())  

    def all_group_members(self):  
        return {r: self.members(r) for r in self.roots()}  

    def __str__(self):  
        return "\n".join("{} {}".format(r, self.members(r)) for r in self.roots())  

N, M = map(int, input().split())  
uf = UnionFind(N)  
A, B = [], []  
for i in range(M):  
    a, b = map(int, input().split())  
    A.append(a)  
    B.append(b)  
A = A[::-1]  
B = B[::-1]  
ans = [N*(N-1)//2]  
for a, b in zip(A, B):  
    if not uf.are_same(a-1, b-1):  
        ans.append(max(0, ans[-1] - uf.size(a-1) * uf.size(b-1)))  
    else:  
        # もともと連結なら不便度は変わらない  
        ans.append(ans[-1])  
    uf.union(a-1, b-1)  
print(*ans[::-1][1:], sep="\n")  

感想

UnionFindとか毎回実装するのはつらすぎるし、いよいよライブラリを作っていきたい。

技術ブログをはじめよう Qrunch(クランチ)は、プログラマの技術アプトプットに特化したブログサービスです
駆け出しエンジニアからエキスパートまで全ての方々のアウトプットを歓迎しております!
or 外部アカウントで 登録 / ログイン する
クランチについてもっと詳しく

この記事が掲載されているブログ

yosakaの技術ブログ。勉強したこととかを書きます。最近は精進の記録が多め。Pythonしか書けない雑魚

よく一緒に読まれる記事

0件のコメント

ブログ開設 or ログイン してコメントを送ってみよう