paizaラーニングレベルアップ問題集の「みんなでしりとり」をやってみた

paiza×Qiita記事投稿キャンペーンということで、paizaラーニングレベルアップ問題集の[みんなでしりとり](https://paiza.jp/works/mondai/b_rank_skillcheck_archive/word_chain)をやってみました。
- - -

問題を解く時は、入出力部分を`main`部に、処理部分を別関数にして、以下の様な雛型を作って
```py
'''Python3の場合'''


def solve('''入力値''') -> set:
    alive = set()  # 出力は集合
    return alive


if __name__ == "__main__":
    '''
    入力値を受け取る
    '''

    # 処理
    answer = solve('''入力値''')

    # 出力
    print(answer)
```
問題文（の要点）をコメントとして記述して考えるのも一つでしょう。
```py
def solve('''入力値''') -> set:
    alive = set()  # 出力は集合
    # 1人目、2人目、...、N人目、1人目、2人目、...という順序で発言

        # 1. 発言は、単語リストにある K 個の単語のうちのいずれかの単語でなければならない。
        # 2. 最初の人以外の発言の頭文字は、直前の人の発言の最後の文字と一緒でなければならない。
        # 3. 今までに発言された単語を発言してはならない。
        # 4. zで終わる単語を発言してはならない。
        # 発言の途中で上のルールを破った人は
            # しりとりから外れる。
            # このとき、後続の人は、ルール2を守る必要はない。
        # 脱落した人を抜いて引き続きしりとりを続けていく。

    # しりとりから脱落せずに残っている人のリストを返却する。
    return alive


if __name__ == "__main__":
    # 1行目にしりとりをする人数を表す整数N、
    # 単語リストに乗っている単語の数を表す整数K、
    # しりとりで行われた発言の数を表す整数Mが
    # この順にスペース区切りで与えられます。

    # 続くK行のうちのi行目(1≦i≦K)には、
    # 単語リストに乗っているi番目の単語を表す文字列d_iが与えられます。

    # 続くM行のうちのj行目(1≦j≦M)には、
    # しりとりで行われたj番目の発言を表す文字列s_jが与えられます。

    # 処理
    answer = solve('''入力値''')

    # 1行目には、最終的にしりとりから脱落せずに残っている人の人数を表す整数 N'を出力
    print(len(answer))

    # 続くN'行のうち、i行目(1≦i≦N')には、
    # 最終的にしりとりから脱落せずに残っている人の番号のうち、
    # 小さい方からi番目のものを出力
    for a in sorted(answer):
        print(a)
```
:::note
出力部は仮置きなので、後で変わります。
:::
これをプログラミングしていきます。
※問題文は添字が$1,2,...,N$で与えられることが多いですが、プログラミングする時は適宜$0,1,...,N-1$で読み換えます。
```py
def solve(n: int, D: set, S: list) -> set:
    # 残っている参加者
    alive = {p for p in range(n)}

    # 0人目、1人目、...、N-1人目、0人目、1人目、...という順序で発言
    player = 0

    # 直前の人の発言
    prev = ""

    # 今までに発言された単語
    used_words = set()

    for s in S:
        # ルール破ったフラグ
        violate = False

        # 1. 発言は、単語リストにある単語のうちのいずれかの単語でなければならない。
        if s not in D:
            violate = True

        # 2. 最初の人以外の発言の頭文字は、直前の人の発言の最後の文字と一緒でなければならない。
        if prev != "" and s[0] != prev[-1]:
            violate = True

        # 3. 今までに発言された単語を発言してはならない。
        if s in used_words:
            violate = True

        # 4. zで終わる単語を発言してはならない。
        if s[-1] == 'z':
            violate = True

        if violate:  # 発言の途中で上のルールを破った人は
            # しりとりから外れる。
            alive.remove(player)

            # このとき、後続の人は、ルール2を守る必要はない。
            prev = ""

        else:
            # 今までに発言された単語セット更新
            used_words.add(s)

            # 直前の人の発言を更新する
            prev = s

        # 脱落した人を抜いて引き続きしりとりを続けていく。
        player = (player + 1) % n
        while player not in alive:
            player = (player + 1) % n

    # 残っている/脱落のリストを返却する。
    return alive


if __name__ == "__main__":
    # 1行目にしりとりをする人数を表す整数N、
    # 単語リストに乗っている単語の数を表す整数K、
    # しりとりで行われた発言の数を表す整数Mが
    # この順にスペース区切りで与えられます。
    n, k, m = map(int, input().split())

    # 続くK行のうちのi行目(1≦i≦K)には、
    # 単語リストに乗っているi番目の単語を表す文字列d_iが与えられます。
    D = set()
    for i in range(k):
        D.add(input())

    # 続くM行のうちのj行目(1≦j≦M)には、
    # しりとりで行われたj番目の発言を表す文字列s_jが与えられます。
    S = [""] * m
    for j in range(m):
        S[j] = input()

    # 処理
    alive = solve(n, D, S)

    # 1行目には、最終的にしりとりから脱落せずに残っている人の人数を表す整数 N'を出力
    print(len(alive))

    # 続くN'行のうち、i行目(1≦i≦N')には、
    # 最終的にしりとりから脱落せずに残っている人の番号のうち、
    # 小さい方からi番目のものを出力
    for player in sorted(alive):  # aliveは0-based indexで処理されている
        print(player + 1)  # 1-based indexで出力
```
　
Pythonでは、入力や初期設定を内包表記で行うと、以下のようになります。
```py
n, k, m = map(int, input().split())
D = {input() for i in range(k)}
S = [input() for j in range(m)]
alive = {p for p in range(n)}
player = 0
prev = ""
for s in S:
    if s not in D or prev and s[0] != prev[-1] or s[-1] == 'z':
        alive.remove(player)
        prev = ""
    else:
        D.remove(s)
        prev = s
    player = (player + 1) % n
    while player not in alive:
        player = (player + 1) % n
print(len(alive))
for p in sorted(alive):
    print(p + 1)
```
コードゴルファーさんは`player=(player+1)%n`を`(p+1)%n`、そして`-~p%n`と書くらしい。