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

• 問題: No.3754 Mischievous Resident (Hard)
• ユーザー: marc2825
• 提出日時: 2026-08-07 11:58:30
• 言語: C++17 (gcc 15.3.0 + boost 1.92.0 + ACL)
• 結果: WA
• 実行時間: -
• コード長: 3,294 bytes
• コンパイル時間: 528 ms
• コンパイル使用メモリ: 103,948 KB
• 実行使用メモリ: 14,472 KB
• 最終ジャッジ日時: 2026-10-02 20:52:32
• 合計ジャッジ時間: 9,139 ms
• ジャッジサーバーID （参考情報）: judge2_0 / judge4_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;
    }

    // 単独での必要操作回数 C[i] の計算
    vector<long long> C(m, 0);
    for (int i = 0; i < m; ++i) {
        if (E[i].s < E[i].g) { // 右へ移動
            long long W = INF;
            if (i + 1 < m) {
                W = max(E[i+1].s, E[i+1].g);
            }
            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) {
                W = min(E[i-1].s, E[i-1].g);
            }
            C[i] = get_C(E[i].s, E[i].g, W, false);
        }
    }

    // DPで全体の最小操作回数を計算
    // dp[i] : 左から i 個のエレベーター(0-indexedで0～i-1)までの合計操作回数の最小値
    vector<long long> dp(m + 1, 0);
    dp[0] = 0;
    dp[1] = C[0];
    for (int i = 1; i < m; ++i) {
        // 1. 直前の状態に自分の基本操作回数を足す（独立して動く場合）
        long long cost_single = dp[i] + C[i];
        
        // 2. 左隣とのペアでの操作回数制約を考慮する
        long long req = get_f(E[i].s - E[i-1].s, E[i].g - E[i-1].g);
        long long cost_pair = dp[i-1] + req;
        
        dp[i+1] = max(cost_single, cost_pair);
    }

    cout << dp[m] << "\n";
}

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