Submission #75823137

---

Source Code Expand

/**
 * @file AHC065_chokudai_v3.cpp
 * @brief AHC065 A - Conveyor Design : multi-loop, slack search, rollout.
 * @details
 *   v3 over AHC065_chokudai_v2.cpp
 *   --------------------------------------------------------------
 *   v2 ranked candidate delivery paths by a *static* proxy: the sum of
 *   exit-distances of the next K boxes (disruptionSum). That snapshot
 *   ignores that delivering box k+1 itself scrambles box k+2, etc.
 *
 *   v3 replaces the proxy for the final choice with a real ROLLOUT.
 *   For each of the top NCAND candidate paths of the current box, it
 *   greedily delivers the next ROLLOUT_R boxes on a scratch grid and
 *   counts the actual operations used. The candidate minimising
 *
 *       (ops to deliver box k) + (ops of the k+1..k+R rollout)
 *
 *   is chosen. Everything is measured in real operations, so no WTURN
 *   unit-matching hack is needed for the final decision (WTURN still
 *   guides the intermediate Chokudai beam, which keeps the cheap proxy).
 *
 *   Topology note: the racetrack move graph equals the full grid graph,
 *   so per-box op-distance is already the Manhattan lower bound. The
 *   only remaining lever is operation sharing across deliveries, which
 *   is exactly what the rollout optimises.
 *
 *   Tunable via env vars: AHC_K, AHC_ITERS, AHC_SLACK, AHC_WTURN,
 *                         AHC_R, AHC_NCAND.
 */

#include <bits/stdc++.h>
using namespace std;
using P = pair<int, int>;

const int N = 20, EXR = 0, EXC = 10;
const double TIME_LIMIT = 1.85;

// Tunable parameters (overridable via environment variables for auto-tuning).
// Defaults set by Optuna + pahcer tuning (50 seeds): avg score ~5.92M.
int K_DISRUPT = 36;           // upcoming boxes feeding the intermediate proxy
int ITERS = 111;              // Chokudai iterations per box delivery
int SLACK = 5;                // max extra operations allowed per delivery
int WTURN = 48;               // op weight for the intermediate proxy score
int ROLLOUT_R = 3;            // boxes greedily rolled out to rank candidates
int NCAND = 48;               // candidate paths re-ranked by rollout

int envInt(const char *name, int def) {
    const char *v = getenv(name);
    return v ? atoi(v) : def;
}

int grid[20][20];                         // current box number, -1 if empty
vector<vector<P>> belts;                  // 20 belts, each 40 cells
int hbelt[20][20], hidx[20][20];          // H-loop id / index for each cell
int vbelt[20][20], vidx[20][20];          // V-loop id / index for each cell
int distm[20][20];                        // BFS op-distance to the exit
int curBox;                               // box currently being delivered

// --- belt layout -----------------------------------------------------------
void buildBelts() {
    belts.assign(20, {});
    for (int k = 0; k < 10; ++k) {                 // horizontal loops 0..9
        int r0 = 2 * k, r1 = 2 * k + 1;
        for (int c = 0; c < 20; ++c) belts[k].push_back({r0, c});
        for (int c = 19; c >= 0; --c) belts[k].push_back({r1, c});
    }
    for (int k = 0; k < 10; ++k) {                 // vertical loops 10..19
        int m = 10 + k, c0 = 2 * k, c1 = 2 * k + 1;
        for (int r = 0; r < 20; ++r) belts[m].push_back({r, c0});
        for (int r = 19; r >= 0; --r) belts[m].push_back({r, c1});
    }
    for (int m = 0; m < 20; ++m)
        for (int t = 0; t < 40; ++t) {
            int r = belts[m][t].first, c = belts[m][t].second;
            if (m < 10) { hbelt[r][c] = m; hidx[r][c] = t; }
            else        { vbelt[r][c] = m; vidx[r][c] = t; }
        }
}

// The four cells reachable from (r,c) by rotating its H/V loop by +-1.
inline void neighbors(int r, int c, int nm[4], int nd[4], int nr[4], int nc[4]) {
    int mh = hbelt[r][c], ih = hidx[r][c];
    int mv = vbelt[r][c], iv = vidx[r][c];
    int bm[4] = {mh, mh, mv, mv};
    int bd[4] = {1, -1, 1, -1};
    int bi[4] = {(ih + 1) % 40, (ih + 39) % 40, (iv + 1) % 40, (iv + 39) % 40};
    for (int e = 0; e < 4; ++e) {
        nm[e] = bm[e]; nd[e] = bd[e];
        nr[e] = belts[bm[e]][bi[e]].first;
        nc[e] = belts[bm[e]][bi[e]].second;
    }
}

// --- BFS distance from the exit (move graph is undirected) -----------------
void buildDist() {
    for (int i = 0; i < 20; ++i)
        for (int j = 0; j < 20; ++j) distm[i][j] = -1;
    queue<P> q;
    distm[EXR][EXC] = 0;
    q.push({EXR, EXC});
    while (!q.empty()) {
        auto [r, c] = q.front(); q.pop();
        int nm[4], nd[4], nr[4], nc[4];
        neighbors(r, c, nm, nd, nr, nc);
        for (int e = 0; e < 4; ++e)
            if (distm[nr[e]][nc[e]] == -1) {
                distm[nr[e]][nc[e]] = distm[r][c] + 1;
                q.push({nr[e], nc[e]});
            }
    }
}

// rotate belt m by direction d on an arbitrary grid
void rotateG(int g[20][20], int m, int d) {
    const auto &b = belts[m];
    int L = 40, old[40];
    for (int x = 0; x < L; ++x) old[x] = g[b[x].first][b[x].second];
    for (int x = 0; x < L; ++x) {
        int y = (x + d + L) % L;
        g[b[y].first][b[y].second] = old[x];
    }
}

// --- Chokudai search state -------------------------------------------------
struct State {
    int g[20][20];
    int tr, tc;                      // current cell of the delivered box
    vector<pair<int, int>> ops;      // operations applied so far
    long long score;
    bool operator<(const State &o) const { return score < o.score; }
};

// Total exit-distance of the next K boxes (cheap intermediate proxy).
long long disruptionSum(const int g[20][20]) {
    long long dis = 0;
    for (int r = 0; r < 20; ++r)
        for (int c = 0; c < 20; ++c) {
            int v = g[r][c];
            if (v > curBox && v <= curBox + K_DISRUPT) dis += distm[r][c];
        }
    return dis;
}

// Intermediate (beam-guiding) score: higher is better.
inline long long scoreOf(const State &s) {
    return -((long long)WTURN * (int)s.ops.size()
             + distm[s.tr][s.tc]
             + disruptionSum(s.g));
}

// Greedily deliver boxes [fromBox, fromBox+R) on grid copy g via shortest
// paths; return the total number of operations used.
int rollout(int g[20][20], int fromBox, int R) {
    int total = 0;
    for (int b = fromBox; b < fromBox + R && b < N * N; ++b) {
        int sr = -1, sc = -1;
        for (int r = 0; r < 20 && sr < 0; ++r)
            for (int c = 0; c < 20; ++c)
                if (g[r][c] == b) { sr = r; sc = c; break; }
        if (sr < 0) break;
        int r = sr, c = sc;
        while (distm[r][c] > 0) {
            int gd = distm[r][c];
            int nm[4], nd[4], nr[4], nc[4];
            neighbors(r, c, nm, nd, nr, nc);
            for (int e = 0; e < 4; ++e)
                if (distm[nr[e]][nc[e]] == gd - 1) {
                    rotateG(g, nm[e], nd[e]);
                    r = nr[e]; c = nc[e];
                    ++total;
                    break;
                }
        }
        g[EXR][EXC] = -1;                            // box b delivered & removed
    }
    return total;
}

// Slack-aware Chokudai search; the top NCAND candidates are re-ranked by a
// real rollout of the following ROLLOUT_R boxes. Returns the chosen sequence.
vector<pair<int, int>> deliverSearch(int sr, int sc, int D, int iters) {
    int budget = D + SLACK;
    vector<priority_queue<State>> qs(budget + 1);

    State s0;
    memcpy(s0.g, grid, sizeof grid);
    s0.tr = sr; s0.tc = sc;
    s0.score = scoreOf(s0);
    qs[0].push(s0);

    vector<State> done;                              // completed delivery paths

    for (int it = 0; it < iters; ++it) {
        for (int d = 0; d < budget; ++d) {
            if (qs[d].empty()) continue;
            State s = qs[d].top(); qs[d].pop();
            int remaining = budget - d;
            int nm[4], nd[4], nr[4], nc[4];
            neighbors(s.tr, s.tc, nm, nd, nr, nc);
            for (int e = 0; e < 4; ++e) {
                int gg = distm[nr[e]][nc[e]];
                if (gg > remaining - 1) continue;
                State ns = s;
                rotateG(ns.g, nm[e], nd[e]);
                ns.tr = nr[e]; ns.tc = nc[e];
                ns.ops.push_back({nm[e], nd[e]});
                ns.score = scoreOf(ns);
                if (gg == 0) {
                    if ((int)done.size() < 4000) done.push_back(ns);
                } else {
                    qs[d + 1].push(ns);
                }
            }
        }
    }
    if (done.empty()) return {};

    // re-rank the most promising candidates with a real rollout
    sort(done.begin(), done.end(),
         [](const State &a, const State &b) { return a.score > b.score; });
    int lim = min((int)done.size(), NCAND);
    int bestIdx = 0;
    long long bestTot = LLONG_MAX;
    for (int i = 0; i < lim; ++i) {
        int g2[20][20];
        memcpy(g2, done[i].g, sizeof g2);
        g2[EXR][EXC] = -1;                           // box k removed
        long long tot = (long long)done[i].ops.size()
                       + rollout(g2, curBox + 1, ROLLOUT_R);
        if (tot < bestTot) { bestTot = tot; bestIdx = i; }
    }
    return done[bestIdx].ops;
}

// Fast deterministic fallback: always take a shortest-progress move.
vector<pair<int, int>> deliverGreedy(int sr, int sc) {
    vector<pair<int, int>> ops;
    int r = sr, c = sc;
    while (distm[r][c] > 0) {
        int g = distm[r][c];
        int nm[4], nd[4], nr[4], nc[4];
        neighbors(r, c, nm, nd, nr, nc);
        for (int e = 0; e < 4; ++e)
            if (distm[nr[e]][nc[e]] == g - 1) {
                ops.push_back({nm[e], nd[e]});
                r = nr[e]; c = nc[e];
                break;
            }
    }
    return ops;
}

int main() {
    K_DISRUPT  = envInt("AHC_K", K_DISRUPT);
    ITERS      = envInt("AHC_ITERS", ITERS);
    SLACK      = envInt("AHC_SLACK", SLACK);
    WTURN      = envInt("AHC_WTURN", WTURN);
    ROLLOUT_R  = envInt("AHC_R", ROLLOUT_R);
    NCAND      = envInt("AHC_NCAND", NCAND);

    int n;
    if (scanf("%d", &n) != 1) return 0;
    for (int i = 0; i < 20; ++i)
        for (int j = 0; j < 20; ++j) scanf("%d", &grid[i][j]);

    buildBelts();
    buildDist();

    // --- output the belt layout --------------------------------------------
    printf("20\n");
    for (int m = 0; m < 20; ++m) {
        printf("40");
        for (auto &p : belts[m]) printf(" %d %d", p.first, p.second);
        printf("\n");
    }

    auto t0 = chrono::steady_clock::now();
    vector<pair<int, int>> allops;

    int nxt = 0;
    if (grid[EXR][EXC] == 0) { grid[EXR][EXC] = -1; nxt = 1; }  // box 0 pre-removed

    for (; nxt < 400; ++nxt) {
        int sr = -1, sc = -1;
        for (int r = 0; r < 20 && sr < 0; ++r)
            for (int c = 0; c < 20; ++c)
                if (grid[r][c] == nxt) { sr = r; sc = c; break; }

        int D = distm[sr][sc];
        curBox = nxt;
        vector<pair<int, int>> seq;

        double el = chrono::duration<double>(chrono::steady_clock::now() - t0).count();

        if (D == 0) {
            int safem = 0;
            for (int m = 0; m < 20; ++m)
                if (m != hbelt[sr][sc] && m != vbelt[sr][sc]) { safem = m; break; }
            seq.push_back({safem, 1});
        } else if (el < TIME_LIMIT) {
            int iters = el < 1.0 ? ITERS
                      : (el < 1.5 ? max(1, ITERS * 45 / 100)
                                  : max(1, ITERS * 15 / 100));
            seq = deliverSearch(sr, sc, D, iters);
            if (seq.empty()) seq = deliverGreedy(sr, sc);
        } else {
            seq = deliverGreedy(sr, sc);
        }

        for (auto [m, d] : seq) rotateG(grid, m, d);
        grid[EXR][EXC] = -1;
        for (auto &o : seq) allops.push_back(o);
    }

    printf("%d\n", (int)allops.size());
    for (auto &o : allops) printf("%d %d\n", o.first, o.second);
    return 0;
}

Submission Info

Judge Result