[伯俊]空港:Union-Find

質問する

http://boj.kr/10775

概要

問題の目立つ文は
すなわち、iii便目を1日からのg igig i(1≦g igig i≦G)の1番目の関門の1つに永久的に停泊しようとし、飛行機がいずれの関門にも停泊できない場合、空港は閉鎖され、その後どの便も到着できない.
すなわち、iii機ごとにg igig i値が入力され、入力値以下の番号のゲートのみが接続される.
また、ドッキング可能な最大飛行機数を得る必要があります.

問題を解く

質問を読んで、ちょっと見るとO(GP)O(GP)O(GP)の答えが思い浮かぶ. 
ドッキングを最大限に行うには,まず,与えられたg igig iに直接対応できるかどうかを判断し,できれば直接ドッキングできる.
直接ドッキングできない場合は、g i 1 gi-1 g i1に相当するゲートが接続されます.
つまり、関門を1つ減らすたびに、飛行機が関門に止まっているかどうかを確認するという大きな問題です.
線形計算では,最悪の場合,ゲートウェイごとにすべてのゲートウェイがチェックされるため,時間的複雑さはO(GP)O(GP)O(GP)O(GP)となる.
でもこのまま解くとTLEは当然爆発します.(範囲が非常に広い)
だから私が考えられる他のアイデアは
g igig iを入力すると、すぐにgigig以下の番号のゲートからドッキング可能なゲートを見つけることができますが、どうなりますか?から出発する.
すぐにはわからなくても、最大限圧縮して、gigig iより小さいゲートに空っぽの情報を伝えたいなら、gig iゲートに停泊して、可能なゲート更新のアイデアをあげましょう. 
すなわち,最初に自分を指す状態から他のノードを指す状態に変更する必要がある.
これはUnionFindアルゴリズムによって解決できる.
空港レイアウトの最初のインデックスはi-1を値とします.(airport[i]=i-1)
これは、g igig iが入力され、g igig i上でドッキングできない場合に、g ii-1 g i1のゲートウェイをドッキングしようとすると理解できる.
次の手順は次のとおりです.

機を直接ドッキングできればドッキングできます.

が直接ドッキングできない場合はfind()関数で空港レイアウトをチェックし、ドッキング可能なゲートウェイを探します.

がドッキング可能なゲートウェイを発見すると、find()関数にパラメータとして渡されるすべてのゲートウェイインデックスの値が、ドッキング可能なゲートウェイインデックスの値に更新される.

たとえば、airport=[1,0,1,2,3,4]では、g i=4 gi=4 g i=4であり、4番と3番ゲートにドッキングできない場合は、2番ゲートをドッキングする必要があり、airportは[1,0,1,1,1,1,1,1,1,1,1,これにより、次回gig iが3または4を入力すると、直接ドッキング可能なステーションを指すことができるので、より効率的にドッキング可能なステーションを見つけることができる.

コード#コード#

import sys
sys.setrecursionlimit(10**5)
In = lambda : sys.stdin.readline().rstrip()
MIS = lambda : map(int, In().split())

def find(x):
  if x<=0:
    return -1
  if not vist[x]:
    vist[x]=1
    return airport[x]
  airport[x] = find(airport[x])
  return airport[x]

G = int(In())
P = int(In())
airport = [i-1 for i in range(G+1)]
vist = [0]*(G+1)
ans=0
for p in range(P):
  g=int(In())
  fg=find(g)
  if fg==-1:
    print(ans)
    sys.exit(0)
    break
  ans+=1
print(ans)