Submission #63336827

---

Source Code Expand

#include <iostream>
#include <vector>
#include <string>
#include <queue>
#include <deque>
#include <chrono>
#include <random>
#include <algorithm>

using namespace std;

vector<pair<int,int>> initial(
    const vector<string>& board,
    const pair<int,int>& start,
    const vector<pair<int,int>>& halls,
    const vector<vector<pair<int,int>>>& obj)
{
    const int dx[] = {-1, 1, 0, 0};
    const int dy[] = {0, 0, -1, 1};
    int N = board.size();
    int end = 0;
    int M = halls.size();
    int K = (M == 1 ? 2*N : N);
    int num = 0;
    for(int i=0;i<M;i++) num += obj[i].size();
    vector<vector<int>> hallPos(N, vector<int>(N, -1));
    for(int i=0;i<M;i++) hallPos[halls[i].first][halls[i].second] = i;
    vector<vector<int>> wallType(N, vector<int>(N, -1));
    vector<vector<int>> wallIdx(N, vector<int>(N, -1));
    for(int i=0;i<obj.size();i++){
        for(int j=0;j<obj[i].size();j++){
            wallType[obj[i][j].first][obj[i][j].second] = i;
            wallIdx[obj[i][j].first][obj[i][j].second] = j;
        }
    }
    vector<pair<int,int>> res;
    pair<int, int> st = start;
    for(int _=0;_<num;_++){
        vector<vector<vector<int>>> dist(1+M*K, vector<vector<int>>(N, vector<int>(N, 1<<30)));
        vector<vector<vector<int>>> enableRoll(M, vector<vector<int>>(N, vector<int>(N, 1000000)));

        for(int i=0;i<M;i++){
            for(int d=0;d<4;d++){
                int x = halls[i].first;
                int y = halls[i].second;
                enableRoll[i][x][y] = 0;
                int m = 0;
                while(true){
                    x += dx[d];
                    y += dy[d];
                    if(x < 0 || N <= x || y < 0 || N <= y) break;
                    if(hallPos[x][y] != -1) break;
                    m = max(m, wallType[x][y] != -1 ? 1 : 0);
                    enableRoll[i][x][y] = m;
                }
            }
        }

        deque<pair<int, pair<int, int>>> qu;
        qu.push_back(make_pair(0, st));
        dist[0][st.first][st.second] = 0;
        while(!qu.empty()){
            auto p = qu.front(); qu.pop_front();
            int state = p.first;
            int x = p.second.first;
            int y = p.second.second;
            int d = dist[state][x][y];
            if(state == 0){
                if(wallIdx[x][y] != -1){
                    int ns = wallType[x][y] * K + wallIdx[x][y] + 1;
                    if(dist[ns][x][y] > d){
                        dist[ns][x][y] = d;
                        qu.push_front(make_pair(ns, make_pair(x, y)));
                    }
                }
            }
            if(state != 0){
                if(hallPos[x][y] == (state-1)/K || enableRoll[(state-1)/K][x][y] == 0){
                    int type = (state-1)/K;
                    int idx = (state-1)%K;
                    res.push_back(make_pair(type, idx));
                    const auto& o = obj[type][idx];
                    wallIdx[o.first][o.second] = -1;
                    wallType[o.first][o.second] = -1;
                    st = make_pair(x, y);
                    break;
                }
            }
            for(int dr=0;dr<4;dr++){
                int nx = x + dx[dr];
                int ny = y + dy[dr];
                if(nx < 0 || N <= nx || ny < 0 || N <= ny) continue;
                if(state != 0){
                    if(wallType[nx][ny] != -1) continue;
                    if(hallPos[nx][ny] >= 0 && hallPos[nx][ny] != (state-1)/K) continue;
                }
                if(dist[state][nx][ny] > d+1){
                    dist[state][nx][ny] = d+1;
                    qu.push_back(make_pair(state, make_pair(nx, ny)));
                }
            }
        }
    }
    return res;
}


pair<int, vector<pair<int,int>>> score(const vector<string>& board, const pair<int,int>& start, const vector<pair<int,int>>& halls, const vector<vector<pair<int,int>>>& obj,
    const vector<pair<int,int>>& order)
{
    const int dx[] = {-1, 1, 0, 0};
    const int dy[] = {0, 0, -1, 1};
    int N = board.size();
    int end = 0;
    int M = halls.size();
    for(int i=0;i<order.size();i++) if (order[i].first != M) end = i+1;
    vector<vector<int>> hallPos(N, vector<int>(N, -1));
    for(int i=0;i<M;i++) hallPos[halls[i].first][halls[i].second] = i;
    vector<vector<vector<int>>> dist(2*end+1, vector<vector<int>>(N, vector<int>(N, 1<<30)));
    vector<vector<vector<pair<int,int>>>> prevAction(2*end+1, vector<vector<pair<int,int>>>(N, vector<pair<int,int>>(N, make_pair(-1, -1))));
    vector<vector<vector<pair<int,pair<int,int>>>>> prev(2*end+1, vector<vector<pair<int,pair<int,int>>>>(N, vector<pair<int,pair<int,int>>>(N, make_pair(-1, make_pair(-1,-1)))));
    vector<vector<vector<int>>> enableRoll(M, vector<vector<int>>(N, vector<int>(N, 1000000)));
    vector<vector<vector<int>>> dirRoll(M, vector<vector<int>>(N, vector<int>(N, 1000000)));
    vector<vector<int>> wall(N, vector<int>(N, 0));
    for(int i=0;i<order.size();i++){
        const auto& o = obj[order[i].first][order[i].second];
        wall[o.first][o.second] = 2*i;
    }
    for(int i=0;i<M;i++){
        for(int d=0;d<4;d++){
            int x = halls[i].first;
            int y = halls[i].second;
            enableRoll[i][x][y] = 0;
            int m = 0;
            while(true){
                x += dx[d];
                y += dy[d];
                if(x < 0 || N <= x || y < 0 || N <= y) break;
                if(hallPos[x][y] != -1) break;
                m = max(m, wall[x][y]);
                enableRoll[i][x][y] = m;
                dirRoll[i][x][y] = (d^1);
            }
        }
    }

    deque<pair<int, pair<int, int>>> qu;
    qu.push_back(make_pair(0, start));
    dist[0][start.first][start.second] = 0;
    int maxState = 0;
    while(!qu.empty()){
        auto p = qu.front(); qu.pop_front();
        int state = p.first;
        int x = p.second.first;
        int y = p.second.second;
        int d = dist[state][x][y];
        maxState = max(maxState, state);
        if(state == 2*end){
            vector<pair<int,int>> res;
            while(state != -1){
                if(prevAction[state][x][y].first != -1){
                    res.push_back(make_pair(prevAction[state][x][y].first, prevAction[state][x][y].second));
                }
                auto q = prev[state][x][y];
                state = q.first;
                x = q.second.first;
                y = q.second.second;
            }
            reverse(res.begin(), res.end());
            return make_pair(res.size(), res);
        }
        const auto& o = order[state/2];
        const auto& objPos = obj[o.first][o.second];
        if(state%2 == 0){
            if(obj[o.first][o.second] == make_pair(x, y)){
                if(dist[state+1][x][y] > d){
                    dist[state+1][x][y] = d;
                    prev[state+1][x][y] = make_pair(state, make_pair(x, y));
                    qu.push_front(make_pair(state+1, make_pair(x, y)));
                }
                continue;
            }
        }
        if(state%2 == 1){
            if(o.first == M){
                for(int i=0;i<M;i++){
                    if(enableRoll[i][x][y] <= state){
                        if(dist[state+1][x][y] > d+1){
                            dist[state+1][x][y] = d+1;
                            prev[state+1][x][y] = make_pair(state, make_pair(x, y));
                            prevAction[state+1][x][y] = make_pair(3, dirRoll[i][x][y]);
                            qu.push_back(make_pair(state+1, make_pair(x, y)));
                        }
                    }
                }
            } else {
                int i = o.first;
                if(enableRoll[i][x][y] <= state){
                    if(dist[state+1][x][y] > d+1){
                        dist[state+1][x][y] = d+1;
                        prev[state+1][x][y] = make_pair(state, make_pair(x, y));
                        prevAction[state+1][x][y] = make_pair(3, dirRoll[i][x][y]);
                        qu.push_back(make_pair(state+1, make_pair(x, y)));
                    }
                }
            }
        }
        for(int dr=0;dr<4;dr++){
            int nx = x + dx[dr];
            int ny = y + dy[dr];
            if(nx < 0 || N <= nx || ny < 0 || N <= ny) continue;
            if(state%2 == 1){
                if(wall[nx][ny] > state) continue;
                if(o.first != M && hallPos[nx][ny] >= 0 && o.first != hallPos[nx][ny]) continue;
            }
            if(state%2 == 0){
                int cdx = abs(x - objPos.first);
                int cdy = abs(y - objPos.second);
                int ndx = abs(nx - objPos.first);
                int ndy = abs(ny - objPos.second);
                if(cdx + cdy < ndx + ndy) continue;
                if(dist[state][nx][ny] > d+1){
                    dist[state][nx][ny] = d+1;
                    prevAction[state][nx][ny] = make_pair(1, dr);
                    prev[state][nx][ny] = make_pair(state, make_pair(x, y));
                    qu.push_back(make_pair(state, make_pair(nx, ny)));
                }
            } else {
                int nextState = state;
                if(hallPos[nx][ny] != -1){
                    nextState++;
                }
                if(dist[nextState][nx][ny] > d+1){
                    dist[nextState][nx][ny] = d+1;
                    prevAction[nextState][nx][ny] = make_pair(1+state%2, dr);
                    prev[nextState][nx][ny] = make_pair(state, make_pair(x, y));
                    qu.push_back(make_pair(nextState, make_pair(nx, ny)));
                }
            }
        }
    }
    return make_pair(maxState, vector<pair<int,int>>());
}

//------------------------------------------------------------------------------
class Timer {
public:
    explicit Timer()
        : mStart(chrono::system_clock::now())
    {}
    void start() { mStart = chrono::system_clock::now(); }
    double msec() const {
        auto t = chrono::system_clock::now();
        return 1e-3 * chrono::duration_cast<std::chrono::microseconds>(t - mStart).count();
    }
private:
    chrono::system_clock::time_point mStart;
};

//------------------------------------------------------------------------------
class XorShift {
public:
    using result_type = uint32_t;
    explicit XorShift(result_type seed){ init(seed); }
    void init(result_type s){
        x = 1812433253U * (s ^ (s >> 30));
        y = 1812433253U * (x ^ (x >> 30)) + 1;
        z = 1812433253U * (y ^ (y >> 30)) + 2;
        w = 1812433253U * (z ^ (z >> 30)) + 3;
    }
    static constexpr result_type min() { return numeric_limits<result_type>::min(); }
    static constexpr result_type max() { return numeric_limits<result_type>::max(); }
    result_type operator() () {
        result_type t = x ^ (x << 11);
        x = y; y = z; z = w;
        return w = (w ^ (w >> 19)) ^ (t ^ (t >> 8));
    }
private:
    result_type x;
    result_type y;
    result_type z;
    result_type w;
};

XorShift rnd(1234567891);

int main(){
    int N, M; cin >> N >> M;
    vector<string> vs(N);
    for(auto& s : vs) cin >> s;
    pair<int,int> start;
    vector<pair<int, int>> halls(M);
    vector<vector<pair<int, int>>> obj(M+1, vector<pair<int, int>>());
    vector<pair<int,int>> dirs = {{1,0}, {-1,0}, {0,1}, {0,-1}};
    for(int i=0;i<N;i++){
        for(int j=0;j<N;j++){
            if(vs[i][j] == 'A'){
                start = make_pair(i,j);
            }
            if(vs[i][j] == 'A' || vs[i][j] == 'B' || vs[i][j] == 'C'){
                halls[vs[i][j]-'A'] = make_pair(i, j);
            }
            if(vs[i][j] == 'a' || vs[i][j] == 'b' || vs[i][j] == 'c'){
                obj[vs[i][j]-'a'].push_back(make_pair(i, j));
            }
            if(vs[i][j] == '@') obj[M].push_back(make_pair(i, j));
        }
    }
    vector<pair<int,int>> order;
    for(int i=0;i<M+1;i++){
        for(int j=0;j<obj[i].size();j++){
            order.push_back(make_pair(i, j));
        }
    }
    cerr << score(vs, start, halls, obj, order).second.size() << endl;
    const auto& initOrder = initial(vs, start, halls, obj);
    cerr << initOrder.size() << " " << order.size() << endl;
    cerr << score(vs, start, halls, obj, initOrder).second.size() << endl;
    for(auto& o : initOrder){
        cerr << o.first << " " << o.second << endl;
    }
    order = initOrder;
    Timer timer;
    const double first_time = timer.msec();
    const double time_limit = 1950;
    const double initial_temp = 2;
    const double final_temp = 0;
    const long long max_iter = 2000000000LL;
    vector<pair<int,int>> bestMove;
    int bestScore = 1000000000;
    int curScore = bestScore;
    for(long long iter=0;iter<max_iter;iter++){
        if(timer.msec() > time_limit){
            cerr << "trynum: " << iter << endl;
            break;
        }

        const double ratio = (timer.msec() - first_time) / (time_limit - first_time);
        const double rev_ratio = 1 - ratio;
        const double temperature = initial_temp + (final_temp - initial_temp) * (1 - rev_ratio * rev_ratio * rev_ratio);


        int p0 = rnd() % order.size();
        int p1 = rnd() % order.size();
        while(order.size() >= 2 && p0 == p1){
            p1 = rnd() % order.size();
        }
        {
            auto tmp = order[p0];
            order.erase(order.begin() + p0);
            if(p0 < p1) p1--;
            order.insert(order.begin() + p1, tmp);
        }
        const auto cur = score(vs, start, halls, obj, order);
        int s = 0;
        if(cur.second.empty()){
            s = 20000 - cur.first;
        } else {
            s = cur.second.size();
        }
        const int dif = s - curScore;

        // スコアがtemperature悪化するときの採用確率は約36.8%
        if(dif < 0 || bernoulli_distribution(exp(-dif/temperature))(rnd)){
            curScore = s;
            if(curScore < bestScore){
                bestScore = curScore;
                bestMove = cur.second;
            }
        } else {
            auto tmp = order[p1];
            order.erase(order.begin() + p1);
            order.insert(order.begin() + p0, tmp);
        }
    }
    for(const auto& p : bestMove){
        cout << p.first << " " << "UDLR"[p.second] << endl;
    }
}

Submission Info

Compile Error

Main.cpp: In function ‘std::vector<std::pair<int, int> > initial(const std::vector<std::__cxx11::basic_string<char> >&, const std::pair<int, int>&, const std::vector<std::pair<int, int> >&, const std::vector<std::vector<std::pair<int, int> > >&)’:
Main.cpp:30:18: warning: comparison of integer expressions of different signedness: ‘int’ and ‘std::vector<std::vector<std::pair<int, int> > >::size_type’ {aka ‘long unsigned int’} [-Wsign-compare]
   30 |     for(int i=0;i<obj.size();i++){
      |                 ~^~~~~~~~~~~
Main.cpp:31:22: warning: comparison of integer expressions of different signedness: ‘int’ and ‘std::vector<std::pair<int, int> >::size_type’ {aka ‘long unsigned int’} [-Wsign-compare]
   31 |         for(int j=0;j<obj[i].size();j++){
      |                     ~^~~~~~~~~~~~~~
Main.cpp:21:9: warning: unused variable ‘end’ [-Wunused-variable]
   21 |     int end = 0;
      |         ^~~
Main.cpp: In function ‘std::pair<int, std::vector<std::pair<int, int> > > score(const std::vector<std::__cxx11::basic_string<char> >&, const std::pair<int, int>&, const std::vector<std::pair<int, int> >&, const std::vector<std::vector<std::pair<int, int> > >&, const std::vector<std::pair<int, int> >&)’:
Main.cpp:116:18: warning: comparison of integer expressions of different signedness: ‘int’ and ‘std::vector<std::pair<int, int> >::size_type’ {aka ‘long unsigned int’} [-Wsign-compare]
  116 |     for(int i=0;i<order.size();i++) if (order[i].first != M) end = i+1;
      |                 ~^~~~~~~~~~~~~
Main.cpp:125:18: warning: comparison of integer expressions of different signedness: ‘int’ and ‘std::vector<std::pair<int, int> >::size_type’ {aka ‘long unsigned int’} [-Wsign-compare]
  125 |     for(int i=0;i<order.size();i++){
      |                 ~^~~~~~~~~~~~~
Main.cpp: In function ‘int main()’:
Main.cpp:311:22: warning: comparison of integer expressions of different signedness: ‘int’ and ‘std::vector<std::pair<int, int> >::size_type’ {aka ‘long unsigned int’} [-Wsign-compare]
  311 |         for(int j=0;j<obj[i].size();j++){
      |                     ~^~~~~~~~~~~~~~

Judge Result