AtCoder 修行日記#70 - Flying Cat Penguin

70日目
ABCのC問題に取り組み中。
茶色レベルのD問題もコンテスト時に触れられるようになってきたので少しづつ解いてこうと思います。

勉強用のコンテンツはここから。
https://kenkoooo.com/atcoder/#/table/

進捗と一言感想

[C問題] 1問(残り138問)

ABC115:Christmas Eve

解答がぱっと思い浮かばず、解説を見てAC。並び替え系の問題でした…。

n, k = map(int , input().split())
hn = [int(input()) for _ in range(n)]
hn.sort()

print(min(hn[i+k-1]-hn[i] for i in range(n-k+1)))

[D問題] 1問(残り176問)

ABC177:Friends

問題としては結構単純にいけるのかなと思ってたのですが、解法を見たら、構造体もしくはクラスを利用しており、結構ややこしめ…。
今回は数珠つなぎでアルゴリズムを書くよりもクラスとメソッドを利用している下記の方を参考にAC。
理解しやすいようにメソッド名などをリファクタリングしました。
Submission #16483630 - AtCoder Beginner Contest 177

class Union:
    def __init__(self, number):
        self.__number = number
        self.parentList = [-1] * number
 
    def getNumber(self):
        return self.__number 

    def getRoot(self, index):
        if self.parentList[index] < 0:
            return index
        root = self.getRoot(self.parentList[index])
        self.parentList[index] = root
        return root
      
    def unite(self, i, j):
        i = self.getRoot(i)
        j = self.getRoot(j)
        if i != j:
            if i > j:
                i, j = j, i
            self.parentList[i] += self.parentList[j]
            self.parentList[j] = i
 
    def getSize(self, i):
        return -self.parentList[self.getRoot(i)]
 
n, m = map(int, input().split())
 
friendUnion = Union(n)
for i in range(m):
  a, b = map(int, input().split())
  friendUnion.unite(a-1, b-1)
 
unionSizes = [friendUnion.getSize(i) for i in range(friendUnion.getNumber())]
print(max(unionSizes))