概要

屋台の位置は時刻が \(N\) 増えると完全に同じ配置に戻ります。
この周期性を使って、状態を「現在時刻 \(\bmod N\)・高橋君の位置・買い物済みの屋台集合」に圧縮し、幅優先探索（BFS）で最短時刻を求めます。

考察

素朴に考えると、各時刻ごとに高橋君は

• 左に移動
• その場に留まる
• 右に移動

の最大 3 通りの行動があります。
これを時刻 \(T\) まで全探索すると \(3^T\) 通りになってしまい、とても間に合いません。

では、何を状態として持てばよいでしょうか。

1. 屋台の動きは時刻 \(N\) 周期

\(i\) 番目の屋台の時刻 \(t\) における位置は

\(((S_i + tD_i - 1) \bmod N) + 1\)

です。ここで時刻を \(t+N\) にすると

\(((S_i + (t+N)D_i - 1) \bmod N) + 1\)

となりますが、\(ND_i \equiv 0 \pmod N\) なので、これは元の位置と同じです。
したがって、各屋台の位置は時刻 \(N\) ごとに繰り返します。
つまり、屋台全体の配置も 時刻 \(\bmod N\) だけ見れば十分 です。

2. 未来を決めるのに必要な情報

ある時点以降の行動可能性を決めるのに必要なのは、次の 3 つだけです。

• 現在時刻の余り \(t \bmod N\)
• 高橋君が今どの区画にいるか
• どの屋台で買い物済みか

逆に、この 3 つが同じなら未来は完全に同じです。
なぜなら、まだ買っていない屋台の位置は時刻の余りで決まり、買い終えた屋台はもう無視してよいからです。

3. 「買い物済み集合」は bitmask で持てる

\(M \leq 10\) なので、買い物済みの屋台集合は bitmask で管理できます。

• bit \(i\) が 1: 屋台 \(i\) は購入済み
• bit \(i\) が 0: まだ未購入

全部買い終えた状態は full = (1<<M)-1 です。

4. 同じ場所にいる屋台はまとめて買う

この問題では、同じ区画に未購入の屋台が複数いると、その全てを同時に買う ことになります。
一部だけ買わない、という選択はできません。

したがって、各

• 時刻の余り \(r\)
• 区画 \(p\)

について、「その時その場所にいる屋台の集合」をあらかじめ bitmask で前計算しておけば、
次の状態の購入済み集合は単に

\(\text{new\_mask} = \text{mask} \;|\; \text{buy\_at}[r][p]\)

で求められます。

5. BFS が最短時刻を与える

1 回の遷移は「時刻が 1 進む」ことに対応します。
つまり全ての辺のコストが 1 のグラフになっているので、BFS を使えば最初にゴールへ到達した時刻が最小です。

---

アルゴリズム

状態を次のように定義します。

• \(r = t \bmod N\)
• \(p =\) 高橋君の現在位置
• \(mask =\) 購入済み屋台集合

ここで状態は「時刻 \(t\) の買い物処理まで終わった直後」を表します。
初期状態は

• 時刻 \(0\)
• 位置は区画 \(1\)
• まだ何も買っていない

です。
なお、問題文の通り 時刻 0 では買い物は発生しない ので、初期 mask は 0 のままです。

前計算 1: その時刻・その区画で買える屋台

0-indexed に直して、各 \(r=0,1,\dots,N-1\) と各位置 \(p=0,1,\dots,N-1\) について

• 時刻の余りが \(r\)
• 区画が \(p\)

のとき、そこにいる屋台の bitmask buy_at[r][p] を作ります。

前計算 2: 高橋君の移動先

位置 \(p\) から次時刻に行ける位置は高々 3 つです。

• そのまま
• 左
• 右

ただし端では範囲外に出ないようにします。

BFS

キューに初期状態を入れて BFS をします。
状態 \((r,p,mask)\) から、次の時刻では

1. 高橋君が \(q\) に移動する
2. 時刻の余りは \(nr=(r+1)\bmod N\)
3. 区画 \(q\) にいる屋台を全部買う

ので、遷移先は

\((nr, q, mask \;|\; buy\_at[nr][q])\)

です。

これを BFS で探索し、購入済み集合が全屋台になったら、その時刻が答えです。
最後まで到達できなければ -1 を出力します。

---

計算量

• 時間計算量: \(O(N^2 2^M)\)
• 空間計算量: \(O(N^2 2^M)\)

補足

状態数は

\(N \times N \times 2^M\)

個です。
各状態からの遷移は高々 3 通りなので、全体でも十分高速です。
制約下では最大でも

\(100 \times 100 \times 2^{10} \approx 10^7\)

状態で収まります。

実装のポイント

• 実装では 0-indexed にすると、屋台位置の計算が
  \(p = (S_i + rD_i) \bmod N\)
  と書けて楽です。
• 時刻 0 では買い物しない ことに注意してください。初期状態で buy_at[0][0] を反映してはいけません。
• buy_at[r][p] を bitmask で持っておくと、同時購入を OR 1 回で処理できます。
• コードでは
  • (時刻の余り, 位置) をまとめた base
  • state = (base << M) | mask

として 1 つの整数にエンコードしており、visited を bytearray で管理して高速化しています。

ソースコード

import sys
from collections import deque

def main():
    input = sys.stdin.readline
    N, M = map(int, input().split())

    S = [0] * M
    D = [0] * M
    for i in range(M):
        s, d = map(int, input().split())
        S[i] = s - 1
        D[i] = d % N

    full = (1 << M) - 1
    NN = N * N

    # buy_at_base[res * N + pos] = bitmask of stalls at that position at that time residue
    buy_at_base = [0] * NN
    for r in range(N):
        offset = r * N
        for i in range(M):
            p = (S[i] + r * D[i]) % N
            buy_at_base[offset + p] |= 1 << i

    # transitions from base state (time residue, position) to next time residue positions
    trans = [None] * NN
    for r in range(N):
        nr_offset = ((r + 1) % N) * N
        row = r * N
        for p in range(N):
            lst = [nr_offset + p]
            if p > 0:
                lst.append(nr_offset + p - 1)
            if p + 1 < N:
                lst.append(nr_offset + p + 1)
            trans[row + p] = tuple(lst)

    total_states = NN * (1 << M)
    visited = bytearray(total_states)

    # state encoding: (base << M) | mask
    start = 0  # time 0, position 0, mask 0
    visited[start] = 1
    q = deque([start])

    time = 0
    shift = M
    buy = buy_at_base
    tr = trans
    vis = visited
    target = full

    while q:
        for _ in range(len(q)):
            state = q.popleft()
            mask = state & target
            base = state >> shift

            for nb in tr[base]:
                nm = mask | buy[nb]
                ns = (nb << shift) | nm
                if not vis[ns]:
                    if nm == target:
                        print(time + 1)
                        return
                    vis[ns] = 1
                    q.append(ns)
        time += 1

    print(-1)

if __name__ == "__main__":
    main()

---

この解説は gpt-5.4-high によって生成されました。