トップ > AtCoder > ABC216D - Pair of Balls

ABC216D - Pair of Balls

AtCoder AtCoder-Beginner Contest Python グラフ グラフ-トポロジカルソート


【関連問題】

考え方

言われたとおりにやって間に合うというのに気付けるか，言われた通りのことが実装できるかがポイント．一番上を毎回すべてスキャンする必要はなく，取り除いた次のボールの状態だけ更新すれば良いから間に合う．

  1. 一番上に2個同じ色があれば取り除く．
  2. 取り除いたら，筒の見ている位置を+1し，その位置のボールの色を一番上にあるものリストに追加する．
  3. 一番上に同じ色がなくなるまで続ける
  4. すべての筒見ている位置が0であればYes, そうでないならNo．


回答例

回答例 - カウンタで管理

筒の一番上にある色数をcounterで管理する（cnt[色] = 個数）．
2個ある色の集合をlistで管理する．
Submission #25417044 - AtCoder Beginner Contest 216

NEXTを定義することで，NEXTが空の場合も統一的に記述できている．
（$k_{i}$が与えられているので，添字範囲で判定もできる）

NEXT[x]は，一番上・一番小さい番号の筒から色xのボールをとったときに，その下のボールの色は何かを与えるリスト．ボールは2コずつしかないから，各xに対してNEXT[x]は1回しか呼ばれない．また，各NEXT[x]の要素数は0か2．

回答例 - 1個ある集合・2個ある集合を別に持つ

筒の一番上に1個ある色の集合・2個ある色の集合を別々のsetで管理する．
Submission #25417044 - AtCoder Beginner Contest 216

回答例 - トポロジカルソート

以下の方法です．取り出せる順に基づいてグラフの辺を張り，グラフがDAG (閉路のない有向グラフ) であることを確かめれば良いです．

トポロジカルソートについては以下：
トポロジカルソート - 競プロはじめました

from collections import deque

N, M = map(int, input().split())
G = [[] for _ in range(N)]
indeg = [0] * N
for _ in range(M):
  k = int(input())
  A = list(map(int, input().split()))
  for f, t in zip(A, A[1:]):
    f -= 1
    t -= 1
    G[f].append(t)
    indeg[t] += 1
    
q = deque()
for i in range(N):
  if indeg[i] == 0:
    q.append(i)
    
ans = []
while q:
  v = q.popleft()
  ans.append(v)
  for chi in G[v]:
    indeg[chi] -= 1
    if indeg[chi] == 0:
      q.append(chi)
      
if len(ans) == N:
  print('Yes')
else:
  print('No')