概要

高橋君が区画を移動しながら、巡回する屋台すべてで買い物をするための最小時刻を求める問題です。 屋台の動きに周期性があることに注目し、高橋君の位置と買い物状況を状態とした最短経路問題（幅優先探索: BFS）に帰着させることで効率的に解くことができます。

考察

1. 屋台の動きの「周期性」に注目する

屋台 \(i\) の時刻 \(t\) における位置は、式 \(((S_i + t \cdot D_i - 1) \bmod N) + 1\) で表されます。 この式からわかる重要な性質は、屋台の位置は時刻 \(t\) を \(N\) で割った余り（\(t \bmod N\)）にのみ依存するということです。

例えば、区画数 \(N = 3\)、初期位置 \(S_1 = 1\)、移動量 \(D_1 = 1\) の屋台を考えてみます。 - 時刻 \(t = 0\) のとき：位置 \(1\) - 時刻 \(t = 1\) のとき：位置 \(2\) - 時刻 \(t = 2\) のとき：位置 \(3\) - 時刻 \(t = 3\) のとき：位置 \(1\) （\(t = 0\) と同じ） - 時刻 \(t = 4\) のとき：位置 \(2\) （\(t = 1\) と同じ）

このように、屋台の配置パターンは \(N\) 秒ごとに全く同じものを繰り返します。

2. 状態をどう定義するか？

すべての屋台で買い物を終える最小時刻を求めたいですが、探索の「状態」に「現在の時刻 \(t\)」をそのまま持たせてしまうと、時刻は無限に増えうるため状態数が無限になってしまいます。

しかし、屋台の配置が \(t \bmod N\) に依存することを利用すると、高橋君と屋台の状況は以下の 3 つの情報だけで完全に表すことができます。

1. 時刻を \(N\) で割った余り: \(r = t \bmod N\) （\(0 \le r < N\)）
2. 高橋君の現在位置: \(p\) （\(1 \le p \le N\)）
3. すでに買い物をした屋台の集合: \(S\) （\(0 \le S < 2^M\) のビットマスク）

この 3 つの情報の組 \((r, p, S)\) を「状態」と定義します。 制約は \(N \le 100, M \le 10\) です。このとき、考えられる状態数の最大値は以下のようになり、十分にコンピュータで扱える広さになります。 $\(\text{状態数} = N \times N \times 2^M = 100 \times 100 \times 1024 \approx 1.02 \times 10^7 \text{（約1000万通り）}\)$

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

初期状態は、時刻 \(t = 0\)、高橋君の位置 \(p = 1\)、買い物済みの屋台 \(S = 0\) なので、状態 \((r, p, S) = (0, 1, 0)\) です。 ここから、1秒経過するごとに「高橋君の移動」→「屋台の移動」→「買い物」という遷移を行います。

すべての遷移のコスト（経過時間）は等しく \(1\) 秒なので、幅優先探索（BFS）を用いることで、すべての屋台で買い物を完了した状態（\(S = 2^M - 1\)）に達する最小の時刻を求めることができます。

---

アルゴリズム

1. 屋台の位置の事前計算

各時刻の余り \(r \in [0, N-1]\) と、各区画 \(p \in [1, N]\) について、その時にその区画に存在する屋台の集合をビットマスク mask[r][p] として前計算しておきます。 これにより、遷移時の「高橋君と同じ区画にいる屋台との買い物」をビット論理和（OR演算）だけで高速に処理できるようになります。

2. 幅優先探索 (BFS)

キュー q と、各状態への最短時刻を記録する配列 dist を用意して探索を行います。

1. 初期化: 初期状態 (r, p, S) = (0, 1, 0) をキューに追加し、dist[(0, 1, 0)] = 0 とします。
2. 探索: キューから現在の状態 (r, p, S) を取り出します。
   • もし S が「すべての屋台で買い物完了」の状態（\((1 \ll M) - 1\)）であれば、その時点の dist の値が答えです。これを出力して終了します。
3. 遷移: 次の時刻の余り \(nr = (r + 1) \bmod N\)、次の時刻 \(ndist = dist + 1\) とします。 高橋君の次の移動先 \(np \in \{p-1, p, p+1\}\)（区画の範囲内のみ）について、以下を行います。
   • 新たに買い物を終える屋台も含めた集合 \(ns = S \cup mask[nr][np]\) を計算します。
   • 状態 (nr, np, ns) が未訪問であれば、dist を \(ndist\) に更新し、キューに追加します。
4. 終了処理: キューが空になっても目標状態に到達しなかった場合は、すべての屋台で買い物をすることは不可能なため -1 を出力します。

---

計算量

• 時間計算量: \(O(N^2 \cdot 2^M)\) 状態数が最大で \(N^2 \cdot 2^M\) であり、各状態からの遷移（高橋君の移動）は「左に移動」「留まる」「右に移動」の最大 3 通りです。各遷移はビット演算などを用いて \(O(1)\) で行えるため、全体の計算量は \(O(N^2 \cdot 2^M)\) となります。 \(N = 100, M = 10\) のとき、遷移回数は最大でも約 \(3 \times 10^7\) 回であり、C++であれば数ミリ秒〜数十ミリ秒で高速に実行可能です。

• 空間計算量: \(O(N^2 \cdot 2^M)\) 探索の訪問状態と最短距離を記録する dist 配列のサイズに依存します。 状態 \((r, p, S)\) を 24 ビットの整数にエンコードすることで、サイズ \(2^{24} \approx 1.6 \times 10^7\) の 1 次元配列（約 64 MB）としてメモリ上に確保でき、一般的なメモリ制限に十分収まります。

---

実装のポイント

• 状態のビットエンコード: 多次元配列（dist[100][100][1024] など）や std::map を使うと、メモリのオーバーヘッドやポインタ参照によるキャッシュミスが発生し、実行時間制限（TLE）になる可能性があります。 提示されたコードでは、状態 \((r, p, S)\) を 1 つの整数に以下のようにビットシフトを用いて埋め込んでいます。

  int next_code = (nr << 17) | (np << 10) | ns;
  

  これにより、非常に高速な 1 次元配列へのアクセスを実現しています。

• インデックスの 0-origin 化: 時刻の剰余 \(r\) は \(0\) から \(N-1\)、屋台のビットマスク \(S\) は \(0\) から \(2^M-1\) で管理することで、余りの計算やビット演算がシンプルになり、バグを減らすことができます。

  ソースコード

#include <iostream>
#include <vector>
#include <queue>

using namespace std;

int main() {
    // Optimize standard I/O operations for performance
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int N, M;
    if (!(cin >> N >> M)) return 0;

    vector<int> S_i(M), D(M);
    for (int i = 0; i < M; ++i) {
        cin >> S_i[i] >> D[i];
    }

    // mask[r][p] stores the bitmask of stalls located at position `p` at time `t` where `t % N == r`
    // r is in [0, N-1], p is in [1, N]
    vector<vector<int>> mask(N, vector<int>(N + 1, 0));
    for (int r = 0; r < N; ++r) {
        for (int i = 0; i < M; ++i) {
            int temp = S_i[i] - 1 + r * D[i];
            int pos = (temp % N + N) % N + 1;
            mask[r][pos] |= (1 << i);
        }
    }

    // Encode state (r, p, S) into a 24-bit integer:
    // r: 7 bits (0-127)
    // p: 7 bits (0-127)
    // S: 10 bits (0-1023)
    // code = (r << 17) | (p << 10) | S
    // Array size is 1 << 24 = 16,777,216 elements (~64 MB)
    vector<int> dist(1 << 24, -1);
    queue<int> q;

    int start_code = (0 << 17) | (1 << 10) | 0;
    dist[start_code] = 0;
    q.push(start_code);

    int target_S = (1 << M) - 1;

    while (!q.empty()) {
        int curr = q.front();
        q.pop();

        int r = curr >> 17;
        int p = (curr >> 10) & 127;
        int S = curr & 1023;

        if (S == target_S) {
            cout << dist[curr] << "\n";
            return 0;
        }

        int nr = r + 1;
        if (nr == N) nr = 0;
        int ndist = dist[curr] + 1;

        // Takahashi moves to p - 1
        if (p > 1) {
            int np = p - 1;
            int ns = S | mask[nr][np];
            int next_code = (nr << 17) | (np << 10) | ns;
            if (dist[next_code] == -1) {
                dist[next_code] = ndist;
                q.push(next_code);
            }
        }
        // Takahashi stays at p
        {
            int np = p;
            int ns = S | mask[nr][np];
            int next_code = (nr << 17) | (np << 10) | ns;
            if (dist[next_code] == -1) {
                dist[next_code] = ndist;
                q.push(next_code);
            }
        }
        // Takahashi moves to p + 1
        if (p < N) {
            int np = p + 1;
            int ns = S | mask[nr][np];
            int next_code = (nr << 17) | (np << 10) | ns;
            if (dist[next_code] == -1) {
                dist[next_code] = ndist;
                q.push(next_code);
            }
        }
    }

    // If target state is unreachable
    cout << -1 << "\n";
    return 0;
}

---

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