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

• 問題: No.3754 Mischievous Resident (Hard)
• ユーザー: marc2825
• 提出日時: 2026-08-07 11:05:12
• 言語: C++17 (gcc 15.3.0 + boost 1.92.0 + ACL)
• 結果: AC
• 実行時間: 61 ms / 2,000 ms
• コード長: 3,240 bytes
• コンパイル時間: 1,738 ms
• コンパイル使用メモリ: 219,228 KB
• 実行使用メモリ: 9,920 KB
• 最終ジャッジ日時: 2026-10-02 20:51:22
• 合計ジャッジ時間: 8,796 ms
• ジャッジサーバーID （参考情報）: judge2_1 / judge4_0

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

ソースコード

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

// X を Y 以下にするのに必要な「切り上げ半減」回数
static inline int hv(ll X, ll Y) {
    int t = 0;
    while (X > Y) { X = (X + 1) / 2; ++t; }
    return t;
}

// [klo,khi] の整数 k で E*k が [lo,hi] に入るものがあるか
static inline bool hitK(ll klo, ll khi, ll lo, ll hi, ll E) {
    if (klo > khi || lo > hi) return false;
    if (lo < 0) lo = 0;
    ll k = (lo + E - 1) / E;
    if (k < klo) k = klo;
    return k <= khi && E * k <= hi;
}

// 隙間 D -> E をちょうど h 手で縮められ、そのうち下側の台が
// 合計 A を担当できるか？   (h = hv(D,E))
static bool feasibleH(ll D, ll E, int h, ll A) {
    if (A == 0) return true;
    ll sig = E * (1LL << h) - D;              // 余裕 σ
    // (1) 第1手は上側の台：p = 下側が担当する最初の手
    for (int p = 2; p <= h; ++p) {
        ll cap = sig >> (p - 1);              // C_max
        if (hitK(1LL << (h - p), (1LL << (h - p + 1)) - 1, A, A + cap, E)) return true;
    }
    // (2) 第1手は下側の台：q = 下側が担当しない最初の手
    for (int q = 2; q <= h + 1; ++q) {
        ll cap = sig >> (q - 1);              // σ - C_min
        ll klo = (1LL << h) - (1LL << (h - q + 1));
        ll khi = (q == h + 1) ? klo : klo + (1LL << (h - q)) - 1;
        if (hitK(klo, khi, A + sig - cap, A + sig, E)) return true;
    }
    return false;
}

// 向かい合うペア：下側が A 上昇、上側が B 下降、隙間 D -> D-A-B
static ll pairCost(ll D, ll A, ll B) {
    ll E = D - A - B;
    int h = hv(D, E);
    return feasibleH(D, E, h, A) ? h : h + 1;
}

int main() {
    int Q;
    if (scanf("%d", &Q) != 1) return 0;
    while (Q--) {
        ll N; int M;
        if (scanf("%lld %d", &N, &M) != 2) return 0;
        vector<pair<ll,ll>> v(M);
        for (int i = 0; i < M; ++i) scanf("%lld", &v[i].first);
        for (int i = 0; i < M; ++i) scanf("%lld", &v[i].second);
        sort(v.begin(), v.end());                 // (S_i, G_i) の辞書順

        // 到達可能性判定（A問題と同じ条件を隣接ペアで確認）
        bool ok = true;
        for (int i = 0; i + 1 < M; ++i) {
            ll s1 = v[i].first,  g1 = v[i].second;
            ll s2 = v[i+1].first, g2 = v[i+1].second;
            if (g1 > g2) { ok = false; break; }
            if (g1 == g2 && !(s1 == s2 && s1 == g1)) { ok = false; break; }
        }
        if (!ok) { puts("-1"); continue; }

        ll ans = 0;
        if (v[0].second   < v[0].first)     ++ans;   // 最下段の台の下降は 1 手
        if (v[M-1].second > v[M-1].first)   ++ans;   // 最上段の台の上昇は 1 手
        for (int j = 0; j + 1 < M; ++j) {
            ll s1 = v[j].first,   g1 = v[j].second;
            ll s2 = v[j+1].first, g2 = v[j+1].second;
            bool up = (g1 > s1), dn = (g2 < s2);     // この隙間を縮める動き
            if (up && dn)  ans += pairCost(s2 - s1, g1 - s1, s2 - g2);
            else if (up) { ll R = max(s2, g2); ans += hv(R - s1, R - g1); }
            else if (dn) { ll L = min(s1, g1); ans += hv(s2 - L, g2 - L); }
        }
        printf("%lld\n", ans);
    }
    return 0;
}