#1175606 (C++17) No.3754 Mischievous Resident (Hard)

• 問題: No.3754 Mischievous Resident (Hard)
• ユーザー: marc2825
• 提出日時: 2026-08-07 11:28:08
• 言語: C++17 (gcc 15.3.0 + boost 1.92.0 + ACL)
• 結果: AC
• 実行時間: 63 ms / 2,000 ms
• コード長: 4,685 bytes
• コンパイル時間: 1,538 ms
• コンパイル使用メモリ: 237,640 KB
• 実行使用メモリ: 9,904 KB
• 最終ジャッジ日時: 2026-10-02 20:52:15
• 合計ジャッジ時間: 8,119 ms
• ジャッジサーバーID （参考情報）: judge2_1 / judge4_1

ファイルパターン	結果
sample	AC * 1
other	AC * 48

ソースコード

#include <bits/stdc++.h>
using namespace std;

using ll = long long;
const ll INF = 1LL << 60;


// --------------------
// 愚直 BFS
// --------------------

struct VectorHash {
    size_t operator()(const vector<int>& v) const {
        size_t h = 0;
        for (int x : v) {
            h ^= hash<int>{}(x) + 0x9e3779b9 + (h << 6) + (h >> 2);
        }
        return h;
    }
};

ll brute(int N, const vector<pair<int, int>>& A) {
    int M = A.size();

    vector<int> S(M), G(M);
    for (int i = 0; i < M; ++i) {
        S[i] = A[i].first;
        G[i] = A[i].second;
    }

    queue<vector<int>> que;
    unordered_map<vector<int>, int, VectorHash> dist;

    dist[S] = 0;
    que.push(S);

    while (!que.empty()) {
        auto X = que.front();
        que.pop();

        int d = dist[X];

        if (X == G) return d;

        // F 階のボタンを押す
        for (int F = 1; F <= N; ++F) {
            int mn = N + 1;

            for (int i = 0; i < M; ++i) {
                mn = min(mn, abs(X[i] - F));
            }

            // 最小距離が同じなら、そのうち任意の1台を選べる
            for (int i = 0; i < M; ++i) {
                if (abs(X[i] - F) != mn) continue;
                if (X[i] == F) continue;

                auto Y = X;
                Y[i] = F;

                if (!dist.count(Y)) {
                    dist[Y] = d + 1;
                    que.push(Y);
                }
            }
        }
    }

    return -1;
}


// --------------------
// 想定解
// --------------------

// 間隔 d の状態から、片側を合計 x だけ逆向きに動かすための最小操作回数
ll calc(ll x, ll d) {
    ll sum = 0;
    int k = 0;
    while (sum < x) {
        sum = sum * 2 + d;
        ++k;
    }
    return k;
}

// 目標間隔 D、逆向きの移動距離 (A, B) について、
// A 側を先に完成させる最小操作回数
ll solve(ll A, ll B, ll D) {
    ll res = INF;

    for (int q = 0; q < 30; ++q) {
        ll H = (1LL << q) * D;
        ll P = (1LL << q) - 1;

        ll l = max(0LL, P - (B - 1) / D);

        // A - D*a <= H
        if (A > H) {
            l = max(l, (A - H + D - 1) / D);
        }

        ll r = min(P, (A - 1) / D);

        if (l > r) continue;

        ll a = l;
        ll x = A - D * a;
        ll y = B - D * (P - a);

        res = min(res, (ll)q + 1 + calc(y, H + x));
    }

    return res;
}

ll fast_solve(int N, int M, vector<pair<int, int>> A) {
    sort(A.begin(), A.end());

    // 到達可能性
    bool ok = true;

    for (int i = 1; i < M; ++i) {
        auto [s1, g1] = A[i - 1];
        auto [s2, g2] = A[i];

        if (g1 > g2 ||
            (g1 == g2 && !(s1 == s2 && s1 == g1))) {
            ok = false;
            break;
        }
    }

    if (!ok) return -1;

    // 1: R, -1: L, 0: S
    vector<int> type(M);

    for (int i = 0; i < M; ++i) {
        auto [s, g] = A[i];

        if (s < g) type[i] = 1;
        if (s > g) type[i] = -1;
    }

    vector<bool> paired(M);
    ll ans = 0;

    // RL ペア
    for (int i = 0; i + 1 < M; ++i) {
        if (type[i] == 1 && type[i + 1] == -1) {
            paired[i] = paired[i + 1] = true;

            auto [s1, g1] = A[i];
            auto [s2, g2] = A[i + 1];

            ll X = g1 - s1;
            ll Y = s2 - g2;
            ll D = g2 - g1;

            ans += min(
                solve(X, Y, D),
                solve(Y, X, D)
            );
        }
    }

    // RL ペアに含まれないエレベーター
    for (int i = 0; i < M; ++i) {
        if (paired[i]) continue;

        auto [s, g] = A[i];

        if (type[i] == 1) {
            if (i + 1 == M) {
                ++ans;
            } else {
                ans += calc(
                    g - s,
                    A[i + 1].second - g
                );
            }
        }

        if (type[i] == -1) {
            if (i == 0) {
                ++ans;
            } else {
                ans += calc(
                    s - g,
                    g - A[i - 1].second
                );
            }
        }
    }

    return ans;
}


int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int Q;
    cin >> Q;

    while (Q--) {
        int N, M;
        cin >> N >> M;

        vector<pair<int, int>> A(M);

        for (auto& [s, g] : A) cin >> s;
        for (auto& [s, g] : A) cin >> g;

        sort(A.begin(), A.end());

        if (N <= 8 && M <= 4) {
            // 小ケース：完全な BFS
            cout << brute(N, A) << '\n';
        } else {
            // 大ケース：想定解
            cout << fast_solve(N, M, A) << '\n';
        }
    }
}