E - Shiritori の解説

何の話かと言うと

atcoder.jp

この問題をネタに「トポロジカルオーダーで処理する」パターンの例を紹介します。

トポロジカルオーダーで処理する話については、まずは、下記の記事を参照してください。

enakai00.hatenablog.com

考え方

上記の記事では、「始状態」を順に削除していくという方法で処理を進めました。一方、今回の問題では、「終状態」を順に削除していく、という発想になります。（厳密にはちょっと違うのですが、詳しくはこの後の説明を読んでください。）

まず、単語 S1 の末尾３文字が単語 S2 の頭の３文字に一致する時に、S1 -> S2 の有効リンクを貼るという処理で単語の集合を有向グラフとみなします。

また、単語 n が自分の手番に回って来たとして、この時の状態価値関数を dp[n] とします。

・このままゲームを続けて確実に負ける場合 : dp[n] = -1
・確実に勝てる場合 : dp[n] = 1

たとえば、遷移先のない「終状態」の単語 n については、これが自分の手番に回ってくると負けが確定するので、dp[n] = -1 と確定します。

すると、単語 n に遷移できる単語 i については、dp[i] = 1 と確定します。（次に単語 n を選べば相手の負けが確定するので。）

この段階で、「終状態」、および、「終状態の１つ手前」の状態について、dp[n] が確定しました。

次に何を考えるかと言うと・・・

dp[i] = 1 である「終状態の１つ手前」の単語 i に関して、この単語 i は相手には渡せません。（これを渡すと負けが確定するから。）つまり、この単語 i は選択対象とはなりえず、はじめから存在しないのと同じことになります。そこで、単語 i に対する既存のリンクをすべて切ってしまいます。

この結果、遷移先が存在しない「終状態 n」が新たに発生して、これに対して dp[n] = -1 と確定します。すると、これの一歩手前の状態は dp[n] = 1 と確定して・・・・と、以下、同様の操作を続けていくことができます。

つまり、「終状態の一歩手前の状態へのリンクを切る」という操作を再帰的に繰り返すことで、勝敗が確定する状態をすべて辿ることができます。キュー（スタック）を使って再帰を実装するとこんな感じになります。

# link_to[n] : ノード n にリンクするノードのリスト
# link_from[n] : ノード n からリンクするノードのリスト
# link_from_count[n] : ノード n から伸びるリンクの数

  q = deque()
  for n in range(1, N+1):
    if link_from_count[n] == 0: # 遷移先の無い単語（終状態）
      q.append(n)

  while q:
    n = q.pop()
    dp[n] = -1 # 単語 n が回ってきたら負け
    for i in link_to[n]:
      if dp[i] != None: # 既に勝ちが決まっているものはスキップ
        continue
      dp[i] = 1 # 単語 n に回せる単語が回ってきたら勝ち
      for j in link_to[i]:
        link_from_count[j] -= 1 # i は選べないので i へのリンクを切る
        if link_from_count[j] == 0: # 新たな終状態が発生
          q.append(j)

先手が単語 n を選ぶとすれば、先手の勝敗は dp[n] の値で決まります。n は先手が後手に渡す単語になるので、dp[n] は後手の勝敗を示す点に注意してください。

  for n in range(1, N+1):
    if dp[n] == -1:
      print('Takahashi')
    elif dp[n] == 1:
      print('Aoki')
    else:
      print('Draw')

あとは、事前準備として、単語間の繋がりを見ながら、リンクのリストを構築する必要がありますが、愚直に二重ループすると TLE するので、ここはうまいことやってください。（最初、ここでTLEしているのに気づかずに、ちょっとはまっちゃいました。）

たとえば、頭、もしくは、末尾の3文字から対応する単語を検索できるディクショナリーを用意します。

  tail_dict = defaultdict(list)
  head_dict = defaultdict(list)

  for n in range(1, N+1):
    S[n] = f.readline().strip()
    head, tail = S[n][:3], S[n][-3:]
    tail_dict[tail].append(n)
    head_dict[head].append(n)
    for i in tail_dict[head]:
      link_from[i].append(n)
      link_to[n].append(i)
      link_from_count[i] += 1
    for i in head_dict[tail]:
      link_from[n].append(i)
      link_to[i].append(n)
      link_from_count[n] += 1

これでOKです。

atcoder.jp