提出 #66918353

---

ソースコード 拡げる

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

// AtCoder Heuristic: Durability-Constrained Transport
// Beam Search Implementation with case-based heuristics
// Compile: g++ -std=c++17 -O2 main.cpp

constexpr int N = 20;
constexpr int MAX_BOX = N*N - 1;   // 399
constexpr int BEAM_W = 64;         // Beam width
constexpr int OP_LIMIT = 16000;    // Max operations (move+pick+drop)

struct Box { int x, y, w, d; };
vector<Box> boxes;
int dist0[N][N];  // Manhattan from (0,0)

struct Held { int id, rem; };
struct State {
    int px=0, py=0;                 // current position
    int ops=0;                      // all ops count
    int moves=0;                    // move count
    array<uint64_t,7> mask{};       // remaining boxes
    vector<Held> stack;             // carried stack
    string log;                     // operations log
    int score=0;                    // heuristic score
};

inline bool has_box(const State &s, int id) {
    return s.mask[id>>6] & (1ULL<<(id&63));
}
inline void remove_box(State &s, int id) {
    s.mask[id>>6] &= ~(1ULL<<(id&63));
}
inline bool all_removed(const State &s) {
    for(auto m: s.mask) if(m) return false;
    return true;
}

// Step one move, update durability, count ops
bool step(State &st, char dir) {
    if(st.ops >= OP_LIMIT) return false;
    st.log.push_back(dir);
    st.ops++; st.moves++;
    if(dir=='U') st.px--;
    else if(dir=='D') st.px++;
    else if(dir=='L') st.py--;
    else if(dir=='R') st.py++;
    if(st.stack.empty()) return true;
    int above = 0;
    for(int i=(int)st.stack.size()-1; i>=0; --i) {
        st.stack[i].rem -= above;
        if(st.stack[i].rem <= 0) return false;
        above += boxes[st.stack[i].id].w;
    }
    return true;
}

bool move_to(State &st, int nx, int ny) {
    while(st.px < nx) if(!step(st,'D')) return false;
    while(st.px > nx) if(!step(st,'U')) return false;
    while(st.py < ny) if(!step(st,'R')) return false;
    while(st.py > ny) if(!step(st,'L')) return false;
    return true;
}

// Heuristic evaluation combining multiple criteria
int evaluate(const State &st) {
    long long val = 0;
    // 1. remaining boxes near origin
    long long sumDist = 0;
    for(int id=0; id<MAX_BOX; ++id) if(has_box(st,id)) {
        auto &b = boxes[id]; sumDist += dist0[b.x][b.y];
    }
    val -= sumDist;
    // 2. number carried
    val += (long long)st.stack.size() * 500;
    // 3. average durability ratio of carried: (d/w)
    if(!st.stack.empty()) {
        double avgRatio = 0;
        for(auto &h: st.stack)
            avgRatio += (double)h.rem / boxes[h.id].w;
        avgRatio /= st.stack.size();
        val += (int)(avgRatio * 100);
    }
    // 4. penalize moves
    val -= st.moves * 5;
    return (int)val;
}

// Beam expansion
vector<State> expand(const State &cur) {
    vector<State> nxt;
    // auto-drop at origin
    if (!cur.stack.empty() && cur.px==0 && cur.py==0) {
        State ns = cur;
        if (ns.ops+1 <= OP_LIMIT) {
            ns.ops++;          // automatic drop, no log
            ns.stack.clear();
            ns.score = evaluate(ns);
            nxt.push_back(move(ns));
        }
        return nxt;
    }
    // case: no box in hand -> pick farthest K in SE, else all
    if (cur.stack.empty()) {
        const int K = 4;
        vector<pair<int,int>> cand;
        for (int id=0; id<MAX_BOX; ++id) if (has_box(cur,id)) {
            auto &b = boxes[id];
            if (b.x>=cur.px && b.y>=cur.py) {
                int d = abs(cur.px-b.x)+abs(cur.py-b.y);
                cand.emplace_back(d,id);
            }
        }
        if (cand.empty()) {
            for (int id=0; id<MAX_BOX; ++id) if (has_box(cur,id)) {
                auto &b = boxes[id];
                int d = abs(cur.px-b.x)+abs(cur.py-b.y);
                cand.emplace_back(d,id);
            }
        }
        sort(cand.begin(),cand.end(),greater<>());
        int take = min(K,(int)cand.size());
        for (int i=0; i<take; ++i) {
            int id = cand[i].second;
            State ns = cur;
            if (!move_to(ns, boxes[id].x, boxes[id].y)) continue;
            if (ns.ops+1 > OP_LIMIT) continue;
            // simulate stacking durability
            int remSteps = dist0[boxes[id].x][boxes[id].y];
            int above=0;
            for (int j=(int)ns.stack.size()-1; j>=0; --j) above+=boxes[ns.stack[j].id].w;
            bool ok=true;
            for (auto &h: ns.stack) {
                if (h.rem < above*remSteps) { ok=false; break; }
            }
            if (!ok) continue;
            // perform pick
            ns.stack.push_back({id, boxes[id].d});
            remove_box(ns,id);
            ns.log.push_back('1'); ns.ops++;
            // ensure return to origin is possible
            {
                State tmp = ns;
                if (!move_to(tmp,0,0)) continue;
            }
            ns.score = evaluate(ns);
            nxt.push_back(move(ns));
        }
    } else {
        // case: carrying -> pick NW candidates or return
        const int K2 = 2;
        vector<pair<double,int>> cand;
        for (int id=0; id<MAX_BOX; ++id) if (has_box(cur,id)) {
            auto &b = boxes[id];
            if (b.x < cur.px && b.y < cur.py) {
                double ratio = double(b.d)/b.w;
                int d = abs(cur.px-b.x)+abs(cur.py-b.y);
                cand.emplace_back(ratio-d*0.1, id);
            }
        }
        if (cand.empty()) {
            for (int id=0; id<MAX_BOX; ++id) if (has_box(cur,id)) {
                auto &b = boxes[id];
                double ratio = double(b.d)/b.w;
                int d = abs(cur.px-b.x)+abs(cur.py-b.y);
                cand.emplace_back(ratio-d*0.1, id);
            }
        }
        sort(cand.begin(), cand.end(), greater<>());
        int take2 = min(K2, (int)cand.size());
        for (int i=0; i<take2; ++i) {
            int id = cand[i].second;
            State ns = cur;
            if (!move_to(ns, boxes[id].x, boxes[id].y)) continue;
            if (ns.ops+1 > OP_LIMIT) continue;
            // staging: simulate return emptiness
            bool reach=false;
            int tx=ns.px, ty=ns.py;
            while (tx>0 || ty>0) {
                if (tx>0) tx--; else if (ty>0) ty--;
                int bid=-1;
                for (int z=0; z<MAX_BOX; ++z) if (boxes[z].x==tx && boxes[z].y==ty && has_box(ns,z)) { bid=z; break; }
                if (bid<0) { reach=true; break; }
            }
            if (!reach) continue;
            // durability check
            int remSteps = dist0[boxes[id].x][boxes[id].y];
            int above=0;
            for (int j=(int)ns.stack.size()-1;j>=0;--j) above+=boxes[ns.stack[j].id].w;
            bool ok=true;
            for (auto &h: ns.stack) if (h.rem < above*remSteps) { ok=false; break; }
            if (!ok) continue;
            ns.stack.push_back({id, boxes[id].d});
            remove_box(ns,id);
            ns.log.push_back('1'); ns.ops++;
            // ensure return
            {
                State tmp=ns;
                if (!move_to(tmp,0,0)) continue;
            }
            ns.score = evaluate(ns);
            nxt.push_back(move(ns));
        }
        // return & auto-drop
        {
            State ns=cur;
            if(move_to(ns,0,0) && !ns.stack.empty() && ns.ops+1<=OP_LIMIT) {
                ns.ops++;
                ns.stack.clear();
                ns.score = evaluate(ns);
                nxt.push_back(move(ns));
            }
        }
    }
    return nxt;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n; cin>>n;
    vector<vector<int>> wg(n,vector<int>(n)), dg(n,vector<int>(n));
    for(int i=0;i<n;i++) for(int j=0;j<n;j++) cin>>wg[i][j];
    for(int i=0;i<n;i++) for(int j=0;j<n;j++) cin>>dg[i][j];
    boxes.reserve(MAX_BOX);
    for(int i=0;i<n;i++) for(int j=0;j<n;j++) if(i||j)
        boxes.push_back({i,j,wg[i][j],dg[i][j]});
    for(int i=0;i<n;i++) for(int j=0;j<n;j++) dist0[i][j] = i+j;
    State init;
    init.mask.fill(0);
    for(int id=0;id<MAX_BOX;++id) init.mask[id>>6] |= 1ULL<<(id&63);
    init.score = evaluate(init);

    vector<State> beam{init}, buf;
    beam.reserve(BEAM_W);
    buf.reserve(BEAM_W*4);
    while(!beam.empty()){
        buf.clear();
        for(auto &s: beam){
            auto v = expand(s);
            for(auto &ns: v) buf.push_back(move(ns));
        }
        if(buf.empty()) break;
        nth_element(buf.begin(), buf.begin()+min((int)buf.size(),BEAM_W), buf.end(),
                    [](auto &a, auto &b){ return a.score > b.score; });
        beam.assign(buf.begin(), buf.begin()+min((int)buf.size(),BEAM_W));
        if(all_removed(beam[0]) && beam[0].stack.empty()) break;
    }
    for(char c: beam[0].log) cout<<c<<"\n";
    return 0;
}

提出情報

ジャッジ結果