Atcoder ABC228 振り返り

　バーチャルで参加しました(175位)．D問題がUnion Findで解けるとは思いもしませんでした．しかも以前実装した形では解くことが出来ず少し書き換える必要がありました．既存のライブラリに手を加えて解く応用力も必要だなと感じさせられました．

A - On and Off【AC】

　良い感じに場合分けして求めます．

S, T, X = map(int, input().split())

if (S < T and S <= X < T) or (T < S and (X < T or S <= X)):
    print("Yes")
else:
    print("No")

B - Takahashi's Secret【AC】

　秘密を知っている事をflag=Trueとして管理します．ansで足していったけれど，True=1であることを使えばsum(flag)としても求められます．

N, X = map(int, input().split())
X -= 1
A = [int(i)-1 for i in input().split()]
flag = [False]*N
ans = 0

while True:
    if flag[X]:
        print(ans)
        break
    flag[X] = True
    ans += 1
    X = A[X]

C - Final Day【AC】

　自分が満点，他が0点を取ったとき自分が最も高い順位を取る事が出来ます．各人の3教科の点数の和を計算し，それをソートしてK番目の人の点数をボーダーとします．他の人は0点を取るのでボーダーは計算したボーダーの点数，自分の点数は既に取った3教科の和＋満点の300点となります．これで自分の点数＞＝ボーダーとなっていれば，K位に入った事になります．
　ソートを少し工夫する必要があります．出力は，入力された生徒の順番通りにしないといけないので，そのままソートすると入力された順番が分からなくなります．lis = [[1, 10], [2, 20], ...]に対し，lis.sort(key=lambda x:x[1])とするとリストの二番目の要素をキーにしてソートされます．lisの中のリストの要素は入れ替わったりしません．よって，P=[[入力された順の番号, 3教科の点数], ...]としてソートすれば，入力された順番を保持したまま，点数でソートできます．点数でソートして，ボーダーを取得したら，リストの1番目をキーにして(これはそのままlis.sort()とすればいいです)ソートすれば入力された順番に戻ります．

N, K = map(int, input().split())
P = []

for i in range(N):
    p1, p2, p3 = map(int, input().split())
    P.append([i, p1+p2+p3])
P.sort(key=lambda x:x[1], reverse=True)
boder = P[K-1][1]
P.sort()

for _, p in P:
    if p + 300 >= boder:
        print("Yes")
    else:
        print("No")

D - Linear Probing【解説AC】

　これがUnion Findで解けるとは思いませんでした．しかも自分の実装したUnion Findクラスでは上手く解けないので書き換える必要がありました．処理を高速化するためのrankは今回はいりません．ある連結グラフからの新しいノードの追加は，＋1のノードからしか起こらないからです．
　親を示すparリストは初期値－1にします．そしてuniteするときはself.par[x] = yとして，xのグループをyを親にするように繋げます．これは今回の問題が，右へ右へとしか新しくノードを繋げないからです．
　A[h]が－1で無く，既に値が埋まっていたとき，右へAを見て-1になるまで移動する必要があります．この移動をいちいち+1ながらループするとTLEになります．そのため-1になる右の端っこを各々のノードに記録しておけば1回の移動で-1へ移動する事が出来ます．この記録にUnion Findのparリストを使います．
　A[h]が-1でなかったら，親リストのh番目に右端の-1のインデックスが書かれているのでそれをhとします．A[h]をxに書き換えます．これで-1となる右端はhではなくh+1となります．hとh+1を併合することによってh以下のグループは親がh+1になります．(なお既にh+1も-1で無かったときは，h+1が属してるグループの親がh以下のグループの親になります．それはUnion Findの関数がちゃんと処理します．)

class Unionfind:
    """ Unionfind

    ノードのグループ化, 同一グループに属しているかの判定
    計算量はO(α(n)) log n より早い

    """
    def __init__(self, n):
        """

        Args:
            n (int): ノードの総数
        """
        self.par = [i for i in range(n)]

    def find(self, x):
        """親が何か探す

        Args:
            x (int): 親を探したいノード番号

        Returns:
            int: 親のノード番号
        """
        if self.par[x] == x:
            return x
        else:
            self.par[x] = self.find(self.par[x])
            return self.par[x]

    def unite(self, x, y):
        """グループの併合

        Args:
            x, y (int): 併合したいノードの番号
        """
        x = self.find(x)
        y = self.find(y)
        self.par[x] = y

N = 2**20
A = [-1]*N
uf = Unionfind(N)
for _ in range(int(input())):
    t, x = map(int, input().split())
    h = x % N
    if t == 1:
        if A[h] != 1:
            h = uf.find(h)
        A[h] = x
        uf.unite(h, (h+1)%N)

    else:
        print(A[h])