概要

一列に並んだ \(N\) 個の区画において、周期的に移動する \(M\) 台の屋台すべてで買い物を完了するために必要な最小の時刻を求める問題です。高橋君の移動と屋台の巡回的な動きを考慮し、幅優先探索（BFS）とビット表現（ビットマスク）を用いて最短時刻を求めます。

考察

1. 屋台の移動の周期性

この問題の最も重要なポイントは、屋台の位置が周期 \(N\) で繰り返されるという点です。 時刻 \(t\) における屋台 \(i\) の位置（0-indexed）は以下のように表されます。 $\(P_i(t) = (S_i - 1 + t \cdot D_i) \bmod N\)$

ここで、\(t\) を \(N\) で割った商を \(k\)、余りを \(R\) とすると、\(t = k \cdot N + R\) と書けます。これを代入すると、 $\((S_i - 1 + (k \cdot N + R) \cdot D_i) \bmod N = (S_i - 1 + k \cdot N \cdot D_i + R \cdot D_i) \bmod N\)\( \)k \cdot N \cdot D_i\( は \)N\( の倍数であるため、\)\bmod N\( を取ると消去されます。したがって、 \)\(P_i(t) = (S_i - 1 + R \cdot D_i) \bmod N\)\( となり、**屋台の位置は時刻 \)t\( を \)N\( で割った余り \)R = t \bmod N$ のみに依存する**ことが分かります。

2. 状態の定義

時刻 \(t\) そのものは無限に大きくなる可能性がありますが、屋台の位置の周期性を利用することで、探索に必要な状態数を有限に抑えることができます。 具体的には、以下の3つの情報の組を「状態」として管理します。 1. 高橋君の現在の位置: \(P\) （\(0 \le P < N\)） 2. 現在の時刻を \(N\) で割った余り: \(R\) （\(0 \le R < N\)） 3. すでに買い物を終えた屋台の集合: \(S\) （\(0 \le S < 2^M\), ビットマスクで表現）

状態数は最大でも \(N \times N \times 2^M\) 通りとなります。 制約は \(N \le 100, M \le 10\) であるため、状態数の最大値は \(100 \times 100 \times 1024 \approx 1.02 \times 10^7\) となり、コンピュータで十分に扱える大きさです。

3. 最短経路問題への帰着

初期状態 \((P=0, R=0, S=0)\) から出発し、時刻を \(1\) ずつ進めながら遷移を行います。すべての屋台で買い物を終えた状態（\(S = 2^M - 1\)）に最も早く到達する経路を求めればよいため、幅優先探索（BFS）を適用できます。

一度訪れた状態 \((P, R, S)\) に再び到達した場合、それ以降の探索はすでに探索済みの経路より遅い（または等しい）時刻になるため、枝刈り（探索の打ち切り）が可能です。

---

アルゴリズム

1. 前処理: 各余り \(R\) （\(0 \le R < N\)）において、各区画 \(pos\) にどの屋台が存在するかをビットマスクで表した配列 shop_mask[R][pos] をあらかじめ計算しておきます。
2. BFSの初期化:
   • 時刻 \(t = 0\)
   • 訪問済みテーブル visited（サイズ \(N \times N \times 2^M\)）を用意し、初期状態 \((P=0, R=0, S=0)\) を訪問済みにします。
   • 現在の探索レイヤー current_layer に初期状態を格納します。
3. 遷移（BFSのループ）: current_layer が空になるまで、時刻 \(t\) を \(1\) ずつ増やしながら以下を繰り返します。
   • 次の時刻 \(nt = t + 1\)、およびその余り \(nR = nt \bmod N\) を求めます。
   • current_layer に含まれる各状態 \((P, S)\) から、高橋君の次の移動先 \(nP \in \{P-1, P, P+1\}\)（範囲内のもの）へ遷移します。
   • 移動後の区画 \(nP\) にある屋台の集合 shop_mask[nR][nP] と、現在の買い物状況 \(S\) の論理和（OR）を取り、新しい買い物状況 \(nS\) を計算します。
   • もし \(nS\) がすべての屋台を含んでいれば（\(nS = 2^M - 1\)）、その時点の時刻 \(nt\) が最小値となるため、これを出力して終了します。
   • 新しい状態 \((nP, nR, nS)\) が未訪問であれば、訪問済みに更新し、次のレイヤー next_layer に追加します。
   • current_layer を next_layer に更新します。
4. 不可能な場合: すべての状態を探索してもすべての屋台を回れずキューが空になった場合は、\(-1\) を出力します。

---

計算量

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

• 状態数は最大で \(N^2 2^M\) 個です。
• 各状態からの遷移（高橋君の移動）は、留まる・左へ移動・右へ移動の最大 \(3\) 通りです。
• したがって、遷移の総数は高々 \(3 N^2 2^M\) 回となり、最悪の場合でも約 \(3 \times 10^7\) 回のループで抑えられます。Pythonではやや重い処理ですが、適切な高速化（後述）を施すことで、実行時間制限内に余裕で間に合わせることができます。

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

• 訪問済みを管理する配列 visited のサイズが \(N \times N \times 2^M\) となり、これが空間計算量のボトルネックとなります。
• \(10^7\) 個の要素を保持する必要がありますが、1バイトの整数（bytearray）で管理することで、約 10 MB 程度のメモリ使用量に抑えられます。

---

実装のポイント

• 多次元配列の平坦化と高速化: Pythonで多次元リスト（例: visited[P][R][S]）を使うと、メモリアクセスのオーバーヘッドが大きくなり制限時間内に間に合わない可能性があります。そのため、3次元のインデックスを1次元のインデックス (P * N + R) * 2^M + S に平坦化し、さらにビット演算（<< や |）を用いて高速にインデックスを計算しています。

• bytearray の使用: 訪問済みフラグの管理には、通常のリストよりもメモリ効率が良く高速な bytearray を使用しています。

• レイヤーごとの一括遷移: 一般的なキュー（collections.deque）を使う代わりに、時刻（深さ）ごとにリスト（current_layer と next_layer）を入れ替える方式をとることで、キューのポップ操作のオーバーヘッドを削減しています。

  ソースコード

import sys

def solve():
    input_data = sys.stdin.read().split()
    if not input_data:
        return
    
    N = int(input_data[0])
    M = int(input_data[1])
    
    S = []
    D = []
    idx = 2
    for _ in range(M):
        S.append(int(input_data[idx]) - 1)
        D.append(int(input_data[idx+1]))
        idx += 2
        
    shop_mask = [[0] * N for _ in range(N)]
    for R in range(N):
        for i in range(M):
            pos = (S[i] + R * D[i]) % N
            shop_mask[R][pos] |= (1 << i)
            
    adj = [[p for p in (P-1, P, P+1) if 0 <= p < N] for P in range(N)]
    
    target_S = (1 << M) - 1
    
    visited = bytearray(N * N * (1 << M))
    visited[0] = 1
    
    current_layer = [0]
    
    t = 0
    shift_M = M
    mask_M = target_S
    
    while current_layer:
        next_layer = []
        nt = t + 1
        nR = nt % N
        shop_mask_nR = shop_mask[nR]
        base_idx = [(nP * N + nR) << shift_M for nP in range(N)]
        
        for P_S in current_layer:
            P = P_S >> shift_M
            S = P_S & mask_M
            
            for nP in adj[P]:
                nS = S | shop_mask_nR[nP]
                if nS == mask_M:
                    print(nt)
                    return
                
                visited_idx = base_idx[nP] | nS
                if not visited[visited_idx]:
                    visited[visited_idx] = 1
                    next_layer.append(nP << shift_M | nS)
                    
        current_layer = next_layer
        t = nt
        
    print(-1)

if __name__ == '__main__':
    solve()

---

この解説は gemini-3.5-flash-thinking によって生成されました。