Union-Find木に出会う

はじめに

電気ハードウェアを得意とするエンジニアが、コンピューターサイエンスに挑みます。主にatCoderとかLeetcodeを主体に、学んだことを共有していきたいと思います。

atCoderの問題をやってみた

atCoderのRange Sumsという問題に出会いました。いや、これがまたなかなかに難しい。時間制限が満たせずまったくダメでした。

自分でやった浅はかな回答

問題を理解するのが難しいが、要するに与えられたヒントが秘密の配列全てを網羅しているかどうかだろ？ということで以下のように安直にやってみた

• Nの配列を作る（初期値0）

• ヒントがもらえたところは1に書き換える

• 最後に配列に0があるかどうか判定

コードは以下。やっていることはあっているが、時間制限を満たせない。一応やろうとしていることは合っているが、アルゴリズムがダメだということ。

#Python3.8
#ダメな解答なのでマネしないように

N,Q=map(int,input().split())

#配列をN個作る
numList = [0] * N

#配列を更新していく。この辺が時間かかってダメ
for jj in range(Q):
  l,r=map(int,input().split())
  
  for ii in range(l - 1, r):
    numList[ii] = 1

#最後0が配列にいたらNoにする
flag = 1
for kk in range(len(numList)):
  if(numList[kk] == 0):
    flag = 0
    break

if(flag == 0):
  print("No")
else:
  print("Yes")

みんなやってたUnion-Find

他の人の解答を見るとどうやらUnion-Findという木を使ったアルゴリズムが必要らしいと気がついた。

アルゴリズム詳細に関しては以下参照

Union-Find木の解説と例題
B-Union Find

やっていることは以下２点だけだと理解した。他の人の解答とUnion-Findのサンプルコードを照らし合わせてみた限りUnion-Findの改造もいらないため、この問題はUnion-Findが必要だと気がつければ解ける問題であると言える。

• 与えられたヒントを木構造でグループ分けしていく

• 最後0とNが同じグループかどうか判定する

最後に

木構造はなんとなく知っていたが、Union-Findは初めて知った。いろんなところで使えそうなアルゴリズムなので、競プロに限らず実務でも使う機会を探してみたいと思います。