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

• 問題: No.3754 Mischievous Resident (Hard)
• ユーザー: marc2825
• 提出日時: 2026-08-07 11:39:40
• 言語: C++17 (gcc 15.3.0 + boost 1.92.0 + ACL)
• 結果: WA
• 実行時間: -
• コード長: 3,924 bytes
• コンパイル時間: 547 ms
• コンパイル使用メモリ: 103,636 KB
• 実行使用メモリ: 12,932 KB
• 最終ジャッジ日時: 2026-10-02 20:52:28
• 合計ジャッジ時間: 9,094 ms
• ジャッジサーバーID （参考情報）: judge2_0 / judge1_0

ファイルパターン	結果
sample	AC * 1
other	AC * 16 WA * 1 TLE * 1 -- * 30

ソースコード

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

const long long INF = 4e18;

struct Elevator {
    long long s, g;
    int id;
};

// 距離 D0 を毎回 ceil(D/2) に置き換えて DG 以下にするための最小回数
long long get_f(long long D0, long long DG) {
    if (D0 <= DG) return 0;
    long long cnt = 0;
    long long D = D0;
    while (D > DG) {
        D = (D + 1) / 2;
        cnt++;
    }
    return cnt;
}

// 座標 S から G へ壁 W を使って移動する基本回数
long long get_C(long long S, long long G, long long W, bool is_right) {
    if (S == G) return 0;
    long long cnt = 0;
    long long X = S;
    if (is_right) {
        while (X < G) {
            long long F = (X + W) / 2;
            if (F >= G) { cnt++; break; }
            X = F; cnt++;
        }
    } else {
        while (X > G) {
            long long F = (X + W + 1) / 2;
            if (F <= G) { cnt++; break; }
            X = F; cnt++;
        }
    }
    return cnt;
}

void solve() {
    int n, m;
    cin >> n >> m;
    vector<long long> 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<Elevator> E(m);
    for (int i = 0; i < m; ++i) {
        E[i] = {S[i], G[i], i};
    }

    // 初期位置でソート
    sort(E.begin(), E.end(), [](const Elevator& a, const Elevator& b) {
        if (a.s != b.s) return a.s < b.s;
        return a.g < b.g;
    });

    // 到達不可能性のチェック（相対順序の逆転や不正な合流）
    bool possible = true;
    for (int i = 0; i < m - 1; ++i) {
        if (E[i].s < E[i+1].s && E[i].g >= E[i+1].g) possible = false;
        if (E[i].s == E[i+1].s && E[i].g > E[i+1].g) possible = false;
        if (E[i].s != E[i+1].s && E[i].g == E[i+1].g) possible = false;
    }

    if (!possible) {
        cout << -1 << "\n";
        return;
    }

    // 各要素の基本移動回数 base_C の計算
    vector<long long> C(m, 0);
    long long total_C = 0;
    for (int i = 0; i < m; ++i) {
        if (E[i].s < E[i].g) { // 右へ移動
            long long W = INF;
            if (i + 1 < m) {
                if (E[i+1].s < E[i+1].g) W = E[i+1].g;
                else if (E[i+1].s > E[i+1].g) W = E[i+1].s;
                else W = E[i+1].s;
            }
            C[i] = get_C(E[i].s, E[i].g, W, true);
        } else if (E[i].s > E[i].g) { // 左へ移動
            long long W = -INF;
            if (i - 1 >= 0) {
                if (E[i-1].s > E[i-1].g) W = E[i-1].g;
                else if (E[i-1].s < E[i-1].g) W = E[i-1].s;
                else W = E[i-1].s;
            }
            C[i] = get_C(E[i].s, E[i].g, W, false);
        }
        total_C += C[i];
    }

    // 向かい合うペアの距離縮小による追加手数の計算
    long long max_add = 0;
    for (int i = 0; i < m; ++i) {
        if (E[i].s < E[i].g) { // i が右へ
            long long sum_C = C[i];
            int nonzero_cnt = (C[i] > 0 ? 1 : 0);
            
            for (int j = i + 1; j < m; ++j) {
                sum_C += C[j];
                if (C[j] > 0) nonzero_cnt++;
                
                if (E[j].s > E[j].g) { // j が左へ（向かい合う）
                    long long req = get_f(E[j].s - E[i].s, E[j].g - E[i].g);
                    if (req - sum_C > max_add) {
                        max_add = req - sum_C;
                    }
                }
                
                // 距離を半分にする回数(req)は高々35回程度なので、
                // 区間内の有効移動回数がそれを超えたら以降は不要
                if (nonzero_cnt > 40) break;
            }
        }
    }

    cout << total_C + max_add << "\n";
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int q;
    if (cin >> q) {
        while (q--) solve();
    }
    return 0;
}