#1185909 (C++23) No.3746 Swap and LIS

• 問題: No.3746 Swap and LIS
• ユーザー: Naru820
• 提出日時: 2026-09-11 18:13:00
• 言語: C++23 (gcc 15.3.0 + boost 1.92.0 + ACL)
• 結果: WA
• 実行時間: -
• コード長: 7,495 bytes
• コンパイル時間: 2,212 ms
• コンパイル使用メモリ: 348,016 KB
• 実行使用メモリ: 14,272 KB
• 最終ジャッジ日時: 2026-09-25 20:52:59
• 合計ジャッジ時間: 24,876 ms
• ジャッジサーバーID （参考情報）: judge2_0 / judge4_1

ファイルパターン	結果
sample	AC * 1
other	AC * 10 WA * 12

ソースコード

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

using ll = long long;
using ull = unsigned long long;

struct XorShift {
    ull x;

    explicit XorShift(ull seed) : x(seed ? seed : 88172645463325252ULL) {}

    ull next() {
        x ^= x << 7;
        x ^= x >> 9;
        return x;
    }

    int randint(int l, int r) {
        return l + (int)(next() % (ull)(r - l + 1));
    }
};

// patience sorting の tails
struct TailState {
    vector<int> d;
    ll sum = 0;

    struct Change {
        int pos;
        int oldValue;
        int newValue;
        bool pushed;
    };

    Change apply(int x) {
        int pos = lower_bound(d.begin(), d.end(), x) - d.begin();

        if (pos == (int)d.size()) {
            d.push_back(x);
            sum += x;
            return {pos, -1, x, true};
        } else {
            int old = d[pos];
            d[pos] = x;
            sum += (ll)x - old;
            return {pos, old, x, false};
        }
    }

    void rollback(const Change& c) {
        if (c.pushed) {
            sum -= c.newValue;
            d.pop_back();
        } else {
            sum += (ll)c.oldValue - c.newValue;
            d[c.pos] = c.oldValue;
        }
    }

    int lisLength() const {
        return (int)d.size();
    }
};

struct Score {
    int len = -1;
    ll penalty = 0;
    ull rnd = 0;
};

static bool betterScore(const Score& a, const Score& b) {
    if (a.len != b.len) return a.len > b.len;
    if (a.penalty != b.penalty) return a.penalty < b.penalty;

    // 完全同点なら乱択
    return a.rnd > b.rnd;
}

class HeuristicSolver {
    int N;
    vector<int> A, B;

    TailState ta, tb;

    int H;
    ll weightA, weightB;
    XorShift rng;

    // root で swap しなかった場合 / した場合の best
    Score best[2];

    void evaluateLeaf(int firstAction) {
        Score s;
        s.len = ta.lisLength() + tb.lisLength();

        // LIS 長が同じなら、
        // tails が小さい状態を「将来性が高い」とみなす。
        //
        // restart ごとに weightA, weightB を微妙に変える。
        s.penalty = ta.sum * weightA + tb.sum * weightB;
        s.rnd = rng.next();

        if (betterScore(s, best[firstAction])) {
            best[firstAction] = s;
        }
    }

    void dfsLookahead(
        int pos,
        int rem,
        int firstAction
    ) {
        if (rem == 0 || pos == N) {
            evaluateLeaf(firstAction);
            return;
        }

        // 軽い枝刈り。
        //
        // 残り rem 個すべてで A,B 両方の LIS が 1 ずつ増えても、
        // 最大で +2*rem。
        if (firstAction != -1 && best[firstAction].len != -1) {
            int upper =
                ta.lisLength() +
                tb.lisLength() +
                2 * rem;

            if (upper < best[firstAction].len) {
                return;
            }
        }

        // action = 0 : swap しない
        // action = 1 : swap する
        //
        // 枝を走査する順番もランダム化しておく。
        int first = rng.next() & 1ULL;

        for (int z = 0; z < 2; z++) {
            int action = first ^ z;

            int x, y;

            if (action == 0) {
                x = A[pos];
                y = B[pos];
            } else {
                x = B[pos];
                y = A[pos];
            }

            auto ca = ta.apply(x);
            auto cb = tb.apply(y);

            int rootAction =
                (firstAction == -1 ? action : firstAction);

            dfsLookahead(
                pos + 1,
                rem - 1,
                rootAction
            );

            tb.rollback(cb);
            ta.rollback(ca);
        }
    }

public:
    HeuristicSolver(
        const vector<int>& A_,
        const vector<int>& B_,
        int H_,
        ll weightA_,
        ll weightB_,
        ull seed
    )
        : N((int)A_.size()),
          A(A_),
          B(B_),
          H(H_),
          weightA(weightA_),
          weightB(weightB_),
          rng(seed) {}

    int run() {
        ta.d.reserve(N);
        tb.d.reserve(N);

        for (int i = 0; i < N; i++) {
            best[0] = Score();
            best[1] = Score();

            dfsLookahead(i, H, -1);

            int action;

            if (betterScore(best[0], best[1])) {
                action = 0;
            } else {
                action = 1;
            }

            // 選ばれた最初の1手だけ本当に確定する。
            if (action == 0) {
                ta.apply(A[i]);
                tb.apply(B[i]);
            } else {
                ta.apply(B[i]);
                tb.apply(A[i]);
            }
        }

        return ta.lisLength() + tb.lisLength();
    }
};

int solveOne(
    const vector<ll>& originalA,
    const vector<ll>& originalB
) {
    int N = originalA.size();

    /*
        座標圧縮。

        LIS では大小関係しか必要ないので、
        1e9 の値を 0..2N-1 程度に圧縮する。

        tails の sum を heuristic score に利用する際にも、
        元の数値の大きさそのものに引っ張られなくなる。
    */
    vector<ll> xs;
    xs.reserve(2 * N);

    for (ll x : originalA) xs.push_back(x);
    for (ll x : originalB) xs.push_back(x);

    sort(xs.begin(), xs.end());
    xs.erase(unique(xs.begin(), xs.end()), xs.end());

    vector<int> A(N), B(N);

    for (int i = 0; i < N; i++) {
        A[i] =
            lower_bound(xs.begin(), xs.end(), originalA[i])
            - xs.begin();

        B[i] =
            lower_bound(xs.begin(), xs.end(), originalB[i])
            - xs.begin();
    }

    /*
        パラメータ。

        LOOKAHEAD = 3:
            かなり軽い

        LOOKAHEAD = 4:
            バランス型

        LOOKAHEAD = 5:
            強めだがかなり重くなる

        RESTARTS を増やすほど乱択探索の本数が増える。
    */
    constexpr int LOOKAHEAD = 5;
    constexpr int RESTARTS = 2;

    int answer = 0;

    // 再現可能な seed にしてある。
    // 本当に毎回ランダムにしたければ chrono を混ぜてもよい。
    ull baseSeed =
        0x123456789abcdefULL
        ^ ((ull)N << 32);

    for (int r = 0; r < RESTARTS; r++) {
        ll wA, wB;

        if (r == 0) {
            /*
                1本目は完全に対称な決定的評価。
            */
            wA = 1000;
            wB = 1000;
        } else {
            /*
                2本目以降では A と B の tails の評価を少し偏らせる。

                LIS 長そのものは常に最優先なので、
                この乱択は「同じ見込み LIS 長の状態」の
                選択にだけ影響する。
            */
            XorShift tmp(baseSeed + r * 1234567ULL);

            wA = tmp.randint(850, 1150);
            wB = 2000 - wA;
        }

        HeuristicSolver solver(
            A,
            B,
            LOOKAHEAD,
            wA,
            wB,
            baseSeed + r * 1000000007ULL
        );

        answer = max(answer, solver.run());
    }

    return answer;
}

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

    int T;
    cin >> T;

    while (T--) {
        int N;
        cin >> N;

        vector<ll> A(N), B(N);

        for (ll& x : A) cin >> x;
        for (ll& x : B) cin >> x;

        cout << solveOne(A, B) << '\n';
    }

    return 0;
}