ABC075_C問題とD問題

問題はこちらから
http://abc075.contest.atcoder.jp

#C問題
橋かどうかを判定する。

自分が考えたのは以下の二つの方法
1.その辺を除いたときにグラフが連結かを判定する,
2.グラフを辿っていき,閉路であるなら含まれる頂点を記録し,含まれていない辺の数を求める

だが,コンテスト内にどちらも実装ができず…
終了後に開設を見てみるとUnionFind法なるものがあるらしいとわかったので
それを使い方法1を実装した。

UnionFindは頂点が負の値をとるので,連結なら頂点が一つ（=負の値が一つ）になることを
判定し,連結判定を行った。

(どなたか方法2での実装など教えていただけませんか？）

##コード

abc075c.py

class UnionFind():
    #負の値はルートで集合の個数
    #正の値は次の要素を返す
    def __init__(self,size):
        self.table = [-1 for _  in range(size)]
    #集合の代表を求める
    def find(self,x):
        while self.table[x] >= 0:
            #根に来た時,self.table[根のindex]は負の値なのでx = 根のindexで値が返される。
            x = self.table[x]
        return x

    #併合
    def union(self,x,y):
        s1 = self.find(x)#根のindex,table[s1]がグラフの高さ
        s2 = self.find(y)
        if s1 != s2:#根が異なる場合
            if self.table[s1] != self.table[s2]:#グラフの高さが異なる場合
                if self.table[s1] < self.table[s2]:
                    self.table[s2] = s1
                else:
                    self.table[s1] = s2
            else:
                #グラフの長さが同じ場合,どちらを根にしても変わらない
                #その際,グラフが1長くなることを考慮する
                self.table[s1] += -1
                self.table[s2] = s1
        return

N,M = list(map(int,input().split()))
A = []
B = []
for i in range(M):
    a,b = map(int,input().split())
    A.append(a-1)
    B.append(b-1)

res = 0

for i in range(M):
    G = UnionFind(N)
    for j in range(M):
        if i != j:
            G.union(A[j],B[j])
    minas = 0
    for k in G.table:
        if k < 0:
            minas += 1
    if minas == 1:
        res += 1


print(M-res)

#D問題
forを長方形の辺決めで4回回し,長方形内部の点を数え上げるのに1回回すので,
O(N^5)出の実装。制約が緩いので間に合う。

だが,長方形を作る際の頂点の選び方である。

高校数学の問題でよくみられる縦,横の辺の組み合わせで長方形の個数を求める問題の
考え方と同じように,x,y座標を別々に取得し,それぞれ二つずつ選び長方形を作ろうとした。

だがこのやり方だと,選んだx座標の区間(下図の黒戦で囲んだ部分)から出ている頂点(赤い点)のy座標を選んでしまうことがあるので,区間内の頂点（青い点）を選ぶようにしないといけない

そこで,x座標をkeyとし,y座標をValueとするデータの保存を行い,処理を行った。

##コード

abc075d.py

from itertools import combinations as comb

def count(x1,y1,x2,y2):
    res = 0
    for x,y in point:
        if x1 <= x <= x2 and y1 <= y <= y2:
            res += 1
    return res 
    
N,K = map(int,input().split())

x = []
point = []
y_dict = {}

for i in range(N):
    a,b = map(int,input().split())
    x.append(a)
    point.append((a,b))
    y_dict[a] = b#yの値はxの値と紐づけしておく

x = sorted(x)
ans = 10**20

number = [i for i in range(N)]
C = list(comb(number,2))

for i,j in C:#組合せで調べる
    y_list = []

    for k in range(i,j+1):#xの指定区間内にある点のy座標を取得しy_listに入れる
        y_list.append(y_dict[x[k]])
        
    y_list = sorted(y_list)
        

    if 2 <= len(y_list):
        number2 = [i for i in range(len(y_list))]
        C_2 = list(comb(number2,2))

        for l,m in C_2:        
                x1 = x[i]
                y1 = y_list[l]
                x2 = x[j]
                y2 = y_list[m]
                n = count(x1,y1,x2,y2)#区間内の点の数
                   
                if K <= n :
                    ans = min(ans,(x2-x1)*(y2-y1)) 
               
print(ans)