paizaラーニングレベルアップ問題集の「長テーブルのうなぎ屋」をやってみた

paiza×Qiita記事投稿キャンペーンということで、paizaラーニングレベルアップ問題集の[長テーブルのうなぎ屋](https://paiza.jp/works/mondai/b_rank_skillcheck_sample/long-table)をやってみました。
- - -
問題を解く時は、入出力部分を`main`部に、処理部分を別関数にして、以下の様な雛型を作って
```py
'''Python3の例'''


def solve('''入力値''') -> int:
    answer = 0  # 出力は整数値なので仮置き
    return answer


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

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

    # 出力
    print(answer)
```
問題文（の要点）をコメントとして記述して考えるのも一つでしょう。
```py
def solve('''入力値''') -> int:
    # テーブルの周りにn個の座席が配置されていて、
    # 座席には、時計回りに1,2,…,nと番号が振られている。
    # （座席番号nの座席と1の座席は隣接している）

    # m個のグループの人達が座席に順番に座りに来る。

        # i番目(1≦i≦m)のグループの人数をa_i人とすると、
        # 座席番号b_iの座席を始点として、そこから時計回りに
        # 連続するa_i個の座席に一斉に座ろうとする。
    
            # いずれか一つでも既に先客に座られている座席があった場合、
                # 一人も座らずにグループ全員で怒って帰ってしまう。

    # 長テーブルの座席に着席出来た人数
    answer = 0

    # 長テーブルの座席に着席出来た人数をカウントする

    # 長テーブルの座席に着席出来ている人数を返却する
    return answer


if __name__ == "__main__":
    # 1行目にはn(座席数)とm(グループ数)が半角スペース区切りで入力されます。

    # i+1行目(1≦i≦m)には2個の整数a_i(グループの人数)と
    # b_i(着席開始座席番号)が半角スペース区切りで入力されます。

    # 最後のグループが座りに来た後、
    # 無事に長テーブルの座席に着席出来ている人数を求める
    answer = solve('''入力値''')

    # 長テーブルの座席に着席出来ている人数を出力する
    print(answer)
```
これをプログラミングしていきます。
※問題文は添字が$1,2,...,N$で与えられることが多いですが、プログラミングする時は適宜$0,1,...,N-1$で読み換えます。
```py
def solve(n: int, m: int, A: list, B: list) -> int:
    # テーブルの周りにn個の座席が配置されていて、
    # 座席には、時計回りに1,2,…,n-2,n-1,0と番号が振られている。
    # （座席番号n-1の座席と0の座席、0の座席と1の座席は隣接している）
    seats = [False] * n  # 空席をFalse、誰かが座ったらTrueとする。

    # m個のグループの人達が座席に順番に座りに来る。
    for i in range(m):
        # i番目(0≦i≦m-1)のグループの人数をa_i人とすると、
        # 座席番号b_iの座席を始点として、そこから時計回りに
        # 連続するa_i個の座席に一斉に座ろうとする。
        can_sit = True
        for j in range(A[i]):
            # 座席番号はnで割った余りで見る
            k = (B[i] + j) % n
            
            if seats[k]:  # いずれか一つでも既に先客に座られている座席があった場合、
                # 一人も座らずにグループ全員で怒って帰ってしまう。
                can_sit = False
                break

        if can_sit:  # 無事に座席に着席出来る
            for j in range(A[i]):
                k = (B[i] + j) % n
                seats[k] = True

    # 長テーブルの座席に着席出来た人数
    answer = 0
    
    # 長テーブルの座席に着席出来た人数をカウントする
    for i in range(n):
        if seats[i]:
            answer += 1

    # 長テーブルの座席に着席出来ている人数を返却する
    return answer


if __name__ == "__main__":
    # 1行目にはn(座席数)とm(グループ数)が半角スペース区切りで入力されます。
    n, m = map(int, input().split())

    # i+1行目(1≦i≦m)には2個の整数a_i(グループの人数)と
    # b_i(着席開始座席番号)が半角スペース区切りで入力されます。
    A = [0] * m
    B = [0] * m
    for i in range(m):
        A[i], B[i] = map(int, input().split())

    # 最後のグループが座りに来た後、
    # 無事に長テーブルの座席に着席出来ている人数を求める
    answer = solve(n, m, A, B)

    # 長テーブルの座席に着席出来ている人数を出力する
    print(answer)
```
:::note
問題文が「客の座っている座席番号を昇順で出力しなさい」の場合、上のプログラムで$0$番席と扱われている席を、$N$番席として最後に出力する必要があります。
:::
- - -
Pythonの場合、`any`関数を用いると以下のように書けます。
```py
n, m = map(int, input().split())
seats = [False] * n
for i in range(m):
    a, b = map(int, input().split())
    if not any(seats[(b + j) % n] for j in range(a)):
        for j in range(a):
            seats[(b + j) % n] = True
print(sum(seats))
```
また、`all`関数を用いると以下のように書けます。
```py
n, m = map(int, input().split())
seats = [False] * n
for i in range(m):
    a, b = map(int, input().split())
    if all(not seats[(b + j) % n] for j in range(a)):
        for j in range(a):
            seats[(b + j) % n] = True
print(sum(seats))
```