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

• 問題: No.3754 Mischievous Resident (Hard)
• ユーザー: marc2825
• 提出日時: 2026-08-19 01:04:30
• 言語: C++17 (gcc 15.3.0 + boost 1.92.0 + ACL)
• 結果: AC
• 実行時間: 92 ms / 2,000 ms
• コード長: 4,812 bytes
• コンパイル時間: 1,266 ms
• コンパイル使用メモリ: 226,340 KB
• 実行使用メモリ: 15,084 KB
• 最終ジャッジ日時: 2026-10-02 20:57:45
• 合計ジャッジ時間: 9,112 ms
• ジャッジサーバーID （参考情報）: judge4_0 / judge1_0

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

ソースコード

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

using ll = long long;

int need_double(ll target, ll cur) {
    // cur * 2^k >= target となる最小 k
    if (cur >= target) return 0;

    ll q = (target + cur - 1) / cur; // ceil(target / cur)

    // ceil(log2(q))
    // q >= 2
    return 64 - __builtin_clzll(q - 1);
}

// 最終 gap = d
// 左から L, 右から R だけ縮める必要があるときの最小操作回数
int calc_gap(ll L, ll R, ll d) {
    ll D = d + L + R;

    int ans = INT_MAX;

    // t 回完全に倍増した後
    ll C = d;

    for (int t = 0; C <= D; ++t) {
        ll E = C - d; // ここまでに復元した総量

        auto check = [&](ll A, ll B) {
            // A 側を先に終わらせる。
            //
            // x = 倍増 prefix の中で A 側に割り当てた量
            //
            // 0 <= x <= A
            // 0 <= E-x <= B
            // A-x <= C
            //
            // かつ x は d の倍数

            ll lo = max({
                0LL,
                E - B,
                A - C
            });

            ll hi = min(A, E);

            ll x = (lo + d - 1) / d * d;

            if (x <= hi) {
                if (x == A) {
                    // A は既に prefix 中に終了している
                    ans = min(ans,
                              t + need_double(D, C));
                } else {
                    // 次の 1 回で A を終了
                    ll nc = C + (A - x);

                    ans = min(ans,
                              t + 1 + need_double(D, nc));
                }
            }

            // x=A は「追加の1回不要」なので、
            // 最小 x とは別にチェックする価値がある。
            if (A % d == 0 && lo <= A && A <= hi) {
                ans = min(ans,
                          t + need_double(D, C));
            }
        };

        // 左を先に終了
        check(L, R);

        // 右を先に終了
        check(R, L);

        if (C > D / 2) break;
        C *= 2;
    }

    return ans;
}

void solve() {
    int Q;
    cin >> Q;

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

        vector<ll> S(M), G(M);
        for (auto &x : S) cin >> x;
        for (auto &x : G) cin >> x;

        vector<pair<ll,ll>> a(M);

        for (int i = 0; i < M; ++i) {
            a[i] = {S[i], G[i]};
        }

        // 同じ初期位置なら G の順番を自由に選べる
        sort(a.begin(), a.end());

        bool ok = true;

        // 異なる初期位置のエレベーターは追い越せない
        for (int i = 0; i + 1 < M; ++i) {
            if (a[i].second > a[i + 1].second) {
                ok = false;
            }
        }

        if (!ok) {
            cout << -1 << '\n';
            continue;
        }

        // 同じ G を持つ複数台は、
        // 全員 S=G でずっと静止していない限り不可能。
        //
        // 静止している重複は 1 台に圧縮する。
        vector<pair<ll,ll>> b;

        for (int i = 0; i < M; ) {
            int j = i + 1;

            while (j < M &&
                   a[j].second == a[i].second) {
                ++j;
            }

            if (j - i >= 2) {
                ll g = a[i].second;

                for (int k = i; k < j; ++k) {
                    if (a[k].first != g) {
                        ok = false;
                    }
                }

                if (!ok) break;

                // 全員 (g -> g)。
                // 位置関係としては 1 台あれば十分。
                b.push_back({g, g});
            } else {
                b.push_back(a[i]);
            }

            i = j;
        }

        if (!ok) {
            cout << -1 << '\n';
            continue;
        }

        int K = (int)b.size();

        ll ans = 0;

        // 一番左がさらに左へ行く場合、
        // 外側には誰もいないので 1 回。
        if (b[0].second < b[0].first) {
            ++ans;
        }

        // 各 gap
        for (int i = 0; i + 1 < K; ++i) {
            ll s1 = b[i].first;
            ll g1 = b[i].second;

            ll s2 = b[i + 1].first;
            ll g2 = b[i + 1].second;

            // 圧縮後は G は strictly increasing
            ll d = g2 - g1;

            // この gap を縮める移動量
            ll L = max(0LL, g1 - s1);
            ll R = max(0LL, s2 - g2);

            ans += calc_gap(L, R, d);
        }

        // 一番右がさらに右へ行く場合も 1 回。
        if (b[K - 1].second > b[K - 1].first) {
            ++ans;
        }

        cout << ans << '\n';
    }
}

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

    solve();
    return 0;
}