ABC262 B Dif:220 『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の灰・茶・緑問題も解説しています！
緑を目指す灰・茶コーダーの方へおすすめ！

【キーワード】
なし

【どう考える？】
「単純無向グラフ」がなにかわからなければ調べよう。
なにやら難しそうな問題に見えるが、一行ずつしっかり意味を確認してみるとそこまでややこしいことはない。制約が小さめなので、全てのa,b,cの組について条件を確認すれば良いとわかる。

【解説】
「単純無向グラフ」とは以下の条件を満たすグラフを言う。
・多重辺がない(頂点①→頂点②の辺が2本以上ある等がない)
・ループがない(頂点①→頂点①等同じ場所に戻る辺がない)
・向きがない(頂点①→頂点②へ進めるなら頂点②→頂点①へも進める)

頂点の数は最大100個なので(a,b,c)の組としてありうるのは100C3=161700通り。
すべての組について
頂点aと頂点bを結ぶ辺が存在する。
頂点bと頂点cを結ぶ辺が存在する。
頂点cと頂点aを結ぶ辺が存在する。
という条件を確認する。

【実装のコツ】
<つながっている頂点の記録>
つながっている頂点の記録には二次元配列を使う。
まず二次元配列connectを作る。初期値は全てFalse。

connect=[[False]*(N+1) for i in range(N+1)]

U,Vを受け取り、U→V,U→Vがつながっている⇔connect[U][V]=True,connect[V][U]=Trueと記録を行う。

for i in range(M):
    # 入力の受け取り
    U,V=map(int,input().split())
    # 頂点Uと頂点Vがつながっている⇔Trueと記録
    connect[U][V]=True
    connect[V][U]=True

<三重ループ>
(a,b,c)の組を確認するため、三重ループを使う。

# a=1~N
for a in range(1,N+1):
    # b=(a+1)~N
    for b in range(a+1,N+1):
        # c=(b+1)~N
        for c in range(b+1,N+1):

このように書くことで
(a,b,c)
(1,2,3)
(1,2,4)
(1,2,5)
…
(1,3,4)
(1,3,5)
(1,3,6)
…
(2,3,4)
(2,3,5)
(2,3,6)
…
(N-2,N-1,N)
という順に代入して処理ができる。

【提出】

# 入力の受け取り
N,M=map(int,input().split())

# つながっている頂点を記録する二次元配列
# 最初は全ての初期値をFalseにする
connect=[[False]*(N+1) for i in range(N+1)]

# M回
for i in range(M):
    # 入力の受け取り
    U,V=map(int,input().split())
    # 頂点Uと頂点Vがつながっている⇔Trueと記録
    connect[U][V]=True
    connect[V][U]=True

# 答え
ans=0

# a=1~N
for a in range(1,N+1):
    # b=(a+1)~N
    for b in range(a+1,N+1):
        # c=(b+1)~N
        for c in range(b+1,N+1):
            # a,b,cが全てつながっていれば
            if connect[a][b]==True and connect[b][c]==True and connect[c][a]==True:
                # 答えにプラス1
                ans+=1

# 答えの出力
print(ans)