#1175121 (C++17) No.3750 Mischievous Resident (Easy)

• 問題: No.3750 Mischievous Resident (Easy)
• ユーザー: marc2825
• 提出日時: 2026-08-06 09:58:40
• 言語: C++17 (gcc 15.3.0 + boost 1.92.0 + ACL)
• 結果: AC
• 実行時間: 36 ms / 2,000 ms
• コード長: 4,541 bytes
• コンパイル時間: 1,357 ms
• コンパイル使用メモリ: 229,752 KB
• 実行使用メモリ: 9,876 KB
• 最終ジャッジ日時: 2026-10-02 20:50:38
• 合計ジャッジ時間: 5,808 ms
• ジャッジサーバーID （参考情報）: judge1_0 / judge4_0

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

ソースコード

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

bool solve_fast(const vector<int>& S, const vector<int>& G) {
    int M = S.size();

    vector<pair<int, int>> A(M);
    for (int i = 0; i < M; ++i) {
        A[i] = {S[i], G[i]};
    }

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

    for (int i = 1; i < M; ++i) {
        auto [s1, g1] = A[i - 1];
        auto [s2, g2] = A[i];

        if (g1 > g2 ||
            (g1 == g2 && !(s1 == s2 && s1 == g1))) {
            return false;
        }
    }

    return true;
}

// 状態 (p_0, ..., p_{M-1}) を N 進数として符号化する。
long long encode(const vector<int>& position,
                 const vector<long long>& power) {
    long long id = 0;

    for (int i = 0; i < (int)position.size(); ++i) {
        id += (position[i] - 1) * power[i];
    }

    return id;
}

bool solve_bruteforce(
    int N,
    const vector<int>& S,
    const vector<int>& G,
    long long state_count
) {
    int M = S.size();

    vector<long long> power(M, 1);
    for (int i = 1; i < M; ++i) {
        power[i] = power[i - 1] * N;
    }

    long long start = encode(S, power);
    long long goal = encode(G, power);

    vector<char> visited(state_count);
    queue<long long> que;

    visited[start] = true;
    que.push(start);

    vector<int> position(M);

    while (!que.empty()) {
        long long state = que.front();
        que.pop();

        if (state == goal) {
            return true;
        }

        long long value = state;
        for (int i = 0; i < M; ++i) {
            position[i] = value % N + 1;
            value /= N;
        }

        for (int F = 1; F <= N; ++F) {
            int minimum_distance = N;

            for (int i = 0; i < M; ++i) {
                minimum_distance =
                    min(minimum_distance, abs(position[i] - F));
            }

            // 最短距離のエレベーターは、どれでも選べる。
            for (int i = 0; i < M; ++i) {
                if (abs(position[i] - F) != minimum_distance) {
                    continue;
                }

                long long next_state =
                    state + 1LL * (F - position[i]) * power[i];

                if (!visited[next_state]) {
                    visited[next_state] = true;
                    que.push(next_state);
                }
            }
        }
    }

    return false;
}

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

    constexpr long long MAX_STATES = 300000;
    constexpr long long MAX_TOTAL_WORK = 50000000;

    long long remaining_work = MAX_TOTAL_WORK;

    int Q;
    cin >> Q;

    for (int test_case = 1; test_case <= Q; ++test_case) {
        int N, M;
        cin >> N >> M;

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

        bool fast_answer = solve_fast(S, G);

        // N^M と、おおよその BFS 計算量 N^M * N * M を評価する。
        long long state_count = 1;
        bool use_bruteforce = true;

        for (int i = 0; i < M; ++i) {
            if (state_count > MAX_STATES / N) {
                use_bruteforce = false;
                break;
            }

            state_count *= N;
        }

        long long estimated_work = 0;

        if (use_bruteforce) {
            if (state_count >
                remaining_work / (1LL * N * M)) {
                use_bruteforce = false;
            } else {
                estimated_work = state_count * N * M;
            }
        }

        bool answer = fast_answer;

        if (use_bruteforce) {
            bool brute_answer =
                solve_bruteforce(N, S, G, state_count);

            // 小ケースでは想定解と愚直解を照合する。
            if (brute_answer != fast_answer) {
                cerr << "Mismatch at test case "
                     << test_case << '\n';
                cerr << "N = " << N << ", M = " << M << '\n';

                cerr << "S:";
                for (int x : S) cerr << ' ' << x;
                cerr << '\n';

                cerr << "G:";
                for (int x : G) cerr << ' ' << x;
                cerr << '\n';

                cerr << "Bruteforce: "
                     << (brute_answer ? "Yes" : "No") << '\n';
                cerr << "Fast: "
                     << (fast_answer ? "Yes" : "No") << '\n';

                return 1;
            }

            answer = brute_answer;
            remaining_work -= estimated_work;
        }

        cout << (answer ? "Yes\n" : "No\n");
    }
}