更新が滞っており申し訳ありません．

停滞していた理由としては，全然解けなかったからです．

進捗

以前の記事で次は

これに挑戦すると言っていました．最初はこのコンテンツの貪欲法に取り組みました．

貪欲法自体はそこそこかけて，Q1-1〜Q1-7まで自力でACできました．その次にグラフ入門のコンテンツに取り組むことにしました．アルゴ式には教科書があるので，それを読みながら進めることでQ3-4まではサクサク解くことができました（3日くらいでここまで到達）．

そこからQ3-5でかなり詰まりました．

algo-method.com

Q3-5について

問題

次の操作を $k = 0,$ ・・・ $N-1$ について順番に行う．

もし $k=0$ なら頂点0に色を塗る
もし $k$ ≠ $0$ なら $i-1$ 回目の操作で色が塗られた頂点と繋がっており、まだ色が塗られていない頂点に色を塗る。

操作 $k$ によって色が塗られた頂点を番号が小さい順に全て求めよ。（ただし $k=i$ のときの操作を操作 $i$ という）

考察

最初の提出

操作自体はシンプル．とにかく頂点0からはじめて隣にある頂点に順番に色を塗っていけばよいので，BFSかな？とすぐ察しがつきました．

で，最初の（ちゃんと）提出したコードがこちら

from collections import deque
#入力を受け取って，頂点と辺の情報をリストGに格納
N, M = map(int, input().split())
G = [ [] for _ in range(N)]
for _ in range(M):
    A, B = map(int,input().split())
    G[A].append(B)
    G[B].append(A)

#彩色済みかどうか
DONE = [ False for _ in range(N)] 

#最初は頂点0から始める
print(0)
DONE[0] = True

#NEXTには，次の操作で色を塗る頂点を格納する．
#最初は頂点0と繋がっている頂点を格納しておく
NEXT = deque(G[0])
l = len(NEXT)

while l > 0:
    for _ in range(l):
　
　　 #NEXTから取り出して，表示，DONE[v]=True（頂点vに色を塗った）とする
        v = NEXT.popleft()
        print( v, end = ' ' if not DONE[v] else '')
        DONE[v] = True

        #頂点vに色を塗ったので，vと繋がっている頂点をNEXTに格納する
        for x in G[v]:
            #すでに色が塗られている頂点と，すでにNEXTに格納されている頂点は除く
            if not DONE[x] and x not in set(NEXT):
                NEXT.append(x)
　
    l = len(NEXT)
    print()

5AC，3WA，2TLEでした．

まぁいろいろよくなかったです．すぐにわかることとして，出力条件の

作 $k$ によって色が塗られた頂点を番号が小さい順に全て求めよ。

番号が小さい順という点を全く考慮していませんでした（読み飛ばしてしまっていました）．実際，WAしたテストケースを見てみると

入力

上記コードの出力

0
3 5 6 
4 1 2

正しい出力

0
3 5 6
1 2 4

となっており，出力の3行目の数字の順番が異なっています．

なので，NEXTに頂点を格納するときにソートしてやれば良いということになります．

次の提出

ということで実装したものがこちら

from collections import deque
N, M = map(int, input().split())
G = [ [] for _ in range(N)]
for _ in range(M):
    A, B = map(int,input().split())
    G[A].append(B)
    G[B].append(A)

#彩色済みかどうか
DONE = [ False for _ in range(N)] 

print(0)
DONE[0] = True
G[0].sort()
NEXT = deque(G[0])
l = len(NEXT)
while NEXT:
    tmp = []
    for _ in range(l):
        v = NEXT.popleft()
        print( v, end = ' ' if not DONE[v] else '')
        DONE[v] = True
        #vの隣接頂点のうちでまだ彩色されていない点をtmpに格納
        #NEXTはキューなのでソートできない
        for x in G[v]:
            if not DONE[x] and x not in NEXT and x not in tmp:
                tmp.append(x)
    tmp.sort()
    for t in tmp:
        NEXT.append(t)
    l = len(NEXT)
    print()

としました．これで1ケースのみTLEであとはACしました．

注意 NEXTにキューを使う必要はありません．なぜかキューを使わないといけないと思い込んでいました．

最後の提出

このTLEがなかなかとれず，アルゴ式さんに

「できません〜」と泣きついたところ

f:id:masuTomo:20211031095842p:plain

さらに

f:id:masuTomo:20211031100025p:plain

ということで修正しました

from collections import deque
N, M = map(int, input().split())
G = [ [] for _ in range(N)]
for _ in range(M):
    A, B = map(int,input().split())
    G[A].append(B)
    G[B].append(A)

#彩色済みかどうか
DONE = [ False for _ in range(N)] 

print(0)
DONE[0] = True
G[0].sort()
NEXT = deque(G[0])
l = len(NEXT)
while NEXT:

    #tmpをセットに変更
    tmp = set()

    for _ in range(l):
        v = NEXT.popleft()
        print( v, end = ' ' if not DONE[v] else '')
        DONE[v] = True
        #vの隣接頂点のうちでまだ彩色されていない点をNEXTに格納
        for x in G[v]:
            if not DONE[x] and x not in set(NEXT) and x not in tmp:
                tmp.add(x)
    tmp = sorted(tmp)
    for t in tmp:
        NEXT.append(t)
    l = len(NEXT)
    print()

まだTLEでしたが，たしかに実行時間で比べるとかなり早くなっていました．

また，このあと

f:id:masuTomo:20211031100444p:plain

f:id:masuTomo:20211031100525p:plain

とアドバイスをいただきました．

後半の

tmp に x を挿入する瞬間に DONE[x] = True にしてしまうことが考えられます！

の部分はおそらく自力では思いつけなかったのではないかと思います．だって，色を塗ったかどうかの判定をリストDONEに格納しています．色を塗ったあとでは遅いのです．NEXTに格納した瞬間に，色を塗ることは確定するのだからそのタイミングでTrueにせよ，と．難しいです．

DONEじゃなくてTODOの気持ちだそうです．

何はともあれ，実装しました．

from collections import deque
N, M = map(int, input().split())
G = [ [] for _ in range(N)]
for _ in range(M):
    A, B = map(int,input().split())
    G[A].append(B)
    G[B].append(A)

#彩色済みかどうか
DONE = [ False for _ in range(N)] 

print(0)
DONE[0] = True
G[0].sort()
NEXT = deque(G[0])

#ここも追記
for g in G[0]:
    DONE[g] = True

l = len(NEXT)

while NEXT:
    tmp = set()
    for _ in range(l):
        v = NEXT.popleft()
        print( v, end = ' ')

        #DONE[v] = True

        #vの隣接頂点のうちでまだ彩色されていない点をNEXTに格納
        for x in G[v]:
            if not DONE[x]:
                tmp.add(x)
                DONE[x] = True

    tmp = sorted(tmp)
    for t in tmp:
        NEXT.append(t)
    l = len(NEXT)
    print()

無事ACです．

おわりに

アルゴ式さんのアドバイスによりなんとかACできました．ちなみに解説のコードはもっとすっきりしていました．（当然キューもつかっていない）．

masuTomo’s blog

競技プログラミングの勉強メモです．主にPythonを使用します．数学の記事も書くかもしれません．

アルゴ式のテスターに選ばれました（20日目?）グラフ入門で苦労しています

進捗

Q3-5について

問題

考察

最初の提出

次の提出

最後の提出

おわりに