#1186597 (C++23) No.3754 Mischievous Resident (Hard)

• 問題: No.3754 Mischievous Resident (Hard)
• ユーザー: marc2825
• 提出日時: 2026-09-12 15:40:33
• 言語: C++23 (gcc 15.3.0 + boost 1.92.0 + ACL)
• 結果: AC
• 実行時間: 54 ms / 2,000 ms
• コード長: 5,090 bytes
• コンパイル時間: 2,418 ms
• コンパイル使用メモリ: 347,536 KB
• 実行使用メモリ: 9,924 KB
• 最終ジャッジ日時: 2026-10-02 21:06:27
• 合計ジャッジ時間: 9,573 ms
• ジャッジサーバーID （参考情報）: judge2_0 / judge1_0

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

ソースコード

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

using int64 = long long;

// total <= current * 2^k を満たす最小の k。
// total, current は正。
int doublingCount(int64 total, int64 current) {
    if (total <= current) {
        return 0;
    }

    // ceil(total / current) - 1
    unsigned long long x =
        static_cast<unsigned long long>((total - 1) / current);

    return 64 - __builtin_clzll(x);
}

// 向かい合う2台の最小操作回数。
// 左の移動距離 left、右の移動距離 right、目的配置の間隔 gap。
int64 solvePair(int64 left, int64 right, int64 gap) {
    const int64 total = left + gap + right;
    int64 answer = numeric_limits<int64>::max();

    int steps = 0;
    int64 width = gap;
    int64 blocks = 0;

    while (width <= total) {
        auto evaluate = [&](int64 l, int64 r) {
            // 幅を steps 回倍増した後、
            // 左へ q * gap、右へ (blocks - q) * gap 広がっている。
            //
            // 右端が初期位置を越えないための下限。
            int64 q = max<int64>(0, blocks - r / gap);

            // 次の1回で左端を初期位置へ到達させるための下限。
            if (l > width) {
                int64 need = (l - width + gap - 1) / gap;
                q = max(q, need);
            }

            if (q > blocks) {
                return;
            }

            int64 expandedLeft = q * gap;

            if (expandedLeft > l) {
                return;
            }

            int64 remainingLeft = l - expandedLeft;

            if (remainingLeft > width) {
                return;
            }

            int64 newWidth = width + remainingLeft;

            int64 candidate = steps;

            if (remainingLeft > 0) {
                ++candidate;
            }

            candidate += doublingCount(total, newWidth);
            answer = min(answer, candidate);
        };

        // 左端を先に到達させる。
        evaluate(left, right);

        // 右端を先に到達させる。
        evaluate(right, left);

        width *= 2;
        blocks = blocks * 2 + 1;
        ++steps;
    }

    return answer;
}

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

    int Q;
    cin >> Q;

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

        vector<int64> S(M), G(M);

        for (int i = 0; i < M; ++i) {
            cin >> S[i];
        }

        for (int i = 0; i < M; ++i) {
            cin >> G[i];
        }

        vector<pair<int64, int64>> elevators(M);

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

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

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

        bool possible = true;

        for (int i = 1; i < M; ++i) {
            if (G[i - 1] > G[i]) {
                possible = false;
                break;
            }

            // 同じ階への合流はできない。
            // 同じ目的階を持つなら、両方とも最初からその階にいる必要がある。
            if (G[i - 1] == G[i]) {
                if (S[i - 1] != G[i - 1] || S[i] != G[i]) {
                    possible = false;
                    break;
                }
            }
        }

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

        int64 answer = 0;

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

            if (S[i] < G[i]) {
                // 右へ動く。
                if (i + 1 < M && S[i + 1] > G[i + 1]) {
                    // 右隣が左へ動くので、2台をまとめて処理。
                    int64 left = G[i] - S[i];
                    int64 right = S[i + 1] - G[i + 1];
                    int64 gap = G[i + 1] - G[i];

                    answer += solvePair(left, right, gap);
                    i += 2;
                } else {
                    if (i + 1 == M) {
                        // 右側にエレベーターがいない。
                        ++answer;
                    } else {
                        int64 initialGap = G[i + 1] - S[i];
                        int64 targetGap = G[i + 1] - G[i];

                        answer += doublingCount(initialGap, targetGap);
                    }

                    ++i;
                }
            } else {
                // 左へ動く。
                // 左隣と向かい合う組なら、すでに組として処理されている。
                if (i == 0) {
                    ++answer;
                } else {
                    int64 initialGap = S[i] - G[i - 1];
                    int64 targetGap = G[i] - G[i - 1];

                    answer += doublingCount(initialGap, targetGap);
                }

                ++i;
            }
        }

        cout << answer << '\n';
    }

    return 0;
}