ABC259 D Dif:947 『AtCoder ABC251～275 ARC140～151 灰・茶・緑問題 超詳細解説』サンプル

この記事は 『AtCoder ABC251～275 ARC140～151 灰・茶・緑問題 超詳細解説』 のサンプルです。

値段：300円(Kindle Unlimited対象)
【kindle】
https://www.amazon.co.jp/dp/B0BRNTM9Z4

【booth(pdf)】
https://sano192.booth.pm/items/4455120

ARC140～151の部分のみ抜粋した廉価版 もあります。
値段：200円(Kindle Unlimited対象)
【kindle】
https://www.amazon.co.jp/dp/B0BRNRXPCV

【booth(pdf)】
https://sano192.booth.pm/items/4455133

【サンプル一覧】
ABC251 A：https://qiita.com/sano192/items/810a4a7d5cf61321bb05
ABC262 B：https://qiita.com/sano192/items/8a9cc91d73a798de6a54
ABC256 C：https://qiita.com/sano192/items/c52d24d0cdf3797a77d7
ABC259 D：https://qiita.com/sano192/items/e39d3636c1ea5d62c1bb

「ものすごく丁寧でわかりやすいABC解説」シリーズをベースに【キーワード】【どう考える？】【別解】を追加し、【解説】と【実装のコツ】を分けることでよりわかりやすく、具体例や図もより豊富に全ての問題の解説を書き直しました！
さらにQiitaでは公開していないARC140～151の灰・茶・緑問題も解説しています！
緑を目指す灰・茶コーダーの方へおすすめ！

【キーワード】
UnionFind

【どう考える？】
乗り換え可能である、すなわち円に共通の部分があるとはどういう条件を満たす場合か、を考えなければならない。知らない、わからない場合は「円 位置関係」などで検索すれば出てくる。
どの円同士が乗り換えできるかわかれば、乗り換え可能な円を辿ってスタートからゴールへたどり着けるかというグラフの問題になる。つまりsが載っている円とtが載っている円が連結かを確認するということで、連結といえばUnionFindと思いつけると簡単。

【解説】
ある円から別の円へと移動できることを「乗り換え可能」と表現する。

円Aの半径をrA、円Bの半径をrBとしたとき、中心間距離をdとした時、乗り換え可能である条件は以下。

これら3つをあわせて
(rB-rA)≤d≤(rB+rA)
となっていれば乗り換え可能と判定できる。
※実装では計算誤差が出ないように距離を二乗している。

乗り換え可能な円はグラフの連結として表せる。
例えば図のような場合、

円1,2,3と円4,5が乗り換え可能だからグラフにすると以下のようになる。

例えば点(sx,sy)が円1、点(tx,ty)が円3に載っていれば円1と円3が連結だから「Yes」になるとわかる。

グラフの連結はUnionFindで管理する。

「UnionFind」
グラフの頂点の連結(Union)と2頂点が連結かを確認する処理(Find)を高速で行えるデータ構造。
詳細はAtCoder公式がわかりやすい解説スライドを作っているのでそちらを見てほしい。ただし理屈がよくわからなくても使い方だけ押さえていればOK。
『AtCoder Typical Contest 001 B - Union Find』
https://atcoder.jp/contests/atc001/tasks/unionfind_a

【実装のコツ】
<UnionFind>
UnionFindはグラフにおける2つの頂点の「連結」(Union)と「連結であるかの判定」(Find)を高速で行うことができるデータ構造。

UnionFindはとてもよく使うデータ構造だが実装は難しい。
灰色、茶色コーダーの人は以下のクラスをコードの最初に丸々コピペして使えれば十分。実装内容まで詳しく知りたいという人は巻末にある「クラス解説：UnionFind」を確認してほしい。

class UnionFind:
    def __init__(self,n):
        self.n=n
        self.parent_size=[-1]*n
    def leader(self,a):
        if self.parent_size[a]<0: return a
        self.parent_size[a]=self.leader(self.parent_size[a])
        return self.parent_size[a]
    def merge(self,a,b):
        x,y=self.leader(a),self.leader(b)
        if x == y: return
        if abs(self.parent_size[x])<abs(self.parent_size[y]):x,y=y,x
        self.parent_size[x] += self.parent_size[y]
        self.parent_size[y]=x
    def same(self,a,b):
        return self.leader(a) == self.leader(b)

「機能」
・初期化【O(N)】：変数名=UnionFind(頂点の数)
・リーダー(根)の確認【だいたいO(1)】：変数名.leader(頂点番号)
・頂点の連結【だいたいO(logN)】：変数名.merge(頂点番号1,頂点番号2)
・連結か確認【だいたいO(1)】：変数名.same(頂点番号1,頂点番号2)
(連結ならTrue,連結でないならならFalseを返す)
UnionFindの計算量解析は難しく、また状況によって操作の計算量は異なるが、だいたい目安として上記の計算量を覚えておけば良い。

「使用例」

# 初期化【O(N)】：変数名=UnionFind(頂点の数)
UF=UnionFind(10)

# 頂点の連結【だいたいO(logN)】：変数名.merge(頂点番号1,頂点番号2)
UF.merge(0,2)
UF.merge(1,3)
UF.merge(3,0)

# 連結か確認【だいたいO(1)】：変数名.same(頂点番号1,頂点番号2)
if UF.same(1,5)==True:
    print("連結")
else:
    print("連結でない")

初期化するときは要素の数をNではなく(N+1)にすることに注意。このクラスは0インデックスでの使用を想定しているため。
・初期化【O(N)】：変数名=UnionFind(頂点の数)

<pypyで提出>
計算量が大きく、pythonでは間に合わないので、提出の際言語に「pypy3」を選んで提出する。
「pypy」はプログラミング言語の一つで、pythonで書いたコードを高速で実行することができる。
(pythonは2sec以内にだいたい10^6回、pypyは2sec以内にだいたい10^8回計算が可能)

【提出】

# pypyで提出

# UnionFind
class UnionFind:
    def __init__(self,n):
        self.n=n
        self.parent_size=[-1]*n
    def leader(self,a):
        if self.parent_size[a]<0: return a
        self.parent_size[a]=self.leader(self.parent_size[a])
        return self.parent_size[a]
    def merge(self,a,b):
        x,y=self.leader(a),self.leader(b)
        if x == y: return
        if abs(self.parent_size[x])<abs(self.parent_size[y]):x,y=y,x
        self.parent_size[x] += self.parent_size[y]
        self.parent_size[y]=x
    def same(self,a,b):
        return self.leader(a) == self.leader(b)

# 入力の受け取り
N=int(input())
sx,sy,tx,ty=map(int,input().split())

# 円の情報
p=[]

# N回
for i in range(N):
    # 入力の受け取り
    x,y,r=map(int,input().split())
    # 記録
    p.append([x,y,r])

# UnionFindを用意
UF=UnionFind(N)

# A=0~(N-1)
for A in range(N):
    # B=(A+1)~(N-1)
    for B in range(A+1,N):
        # 円A,Bの座標と半径を取り出し
        xA,yA,rA=p[A]
        xB,YB,rB=p[B]
 
        # 中心間距離の二乗
        d=(xA-xB)**2+(yA-YB)**2
 
        # 乗り換え可能なら
        if (rB-rA)**2<=d<=(rB+rA)**2:
            # 連結
            UF.merge(A, B)

# スタートの点が載っている円
Start=[]
# ゴールの点が載っている円
Goal=[]

# i=0~(N-1)
for i in range(N):
    # i番目の円の中心、半径の取り出し
    xi,yi,ri=p[i]
 
    # スタートの点が円周上にあれば
    if (sx-xi)**2+(sy-yi)**2==ri**2:
        # 記録
        Start.append(i)
 
    # ゴールの点が円周上にあれば
    if (tx-xi)**2+(ty-yi)**2==ri**2:
        # 記録
        Goal.append(i)

# x：スタートの点が載っている円
for x in Start:
    # y：ゴールの点が載っている円
    for y in Goal:
        # 連結なら
        if UF.same(x,y)==True:
            # 「Yes」を出力
            print("Yes")
            # 終了
            exit()

# 「No」を出力
print("No")