Submission #1173976


Source Code Expand

// Template {{{
#include <bits/stdc++.h>
#define REP(i,n) for(int i=0; i<(int)(n); ++i)
using namespace std;
typedef long long LL;

#ifdef LOCAL
#include "contest.h"
#else
#define error(args...) 
#endif

inline bool valid(int x, int w) { return 0 <= x && x < w; }

void iostream_init() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.setf(ios::fixed);
    cout.precision(12);
}
//}}}

const int WIDTH = 30;
const int HEIGHT = 30;
const int C = 450;
const int TURN = 10000;
int H, W, K, T;
int SX[C], SY[C];
int GX[C], GY[C];

void input() {
    cin >> H >> W >> K >> T;
    REP(i, K) cin >> SY[i] >> SX[i] >> GY[i] >> GX[i];
    REP(i, K) SX[i]--;
    REP(i, K) SY[i]--;
    REP(i, K) GX[i]--;
    REP(i, K) GY[i]--;
}

const int dxs[4] = {1, 0, -1, 0};
const int dys[4] = {0, 1, 0, -1};

int get_move(int dx, int dy) {
    if(dx == 1) {
        return 0;
    } else if(dx == -1) {
        return 2;
    } else if(dy == 1) {
        return 1;
    } else if(dy == -1) {
        return 3;
    } else {
        return 4;
    }
}

char move_to_char(int m) {
    string D = "RDLU-";
    return D[m];
}

int calc_score(int X[C], int Y[C], int turn) {
    int diff = 0;
    REP(i, C) diff += abs(X[i] - GX[i]);
    REP(i, C) diff += abs(Y[i] - GY[i]);
    return (20 + diff) * (1000 + turn);
}

int calc_near(int X[C], int Y[C]) {
    bool grid[HEIGHT][WIDTH] = {};
    REP(i, C) grid[Y[i]][X[i]] = true;
    int res = 0;
    REP(i, C) if(X[i] != GX[i] || Y[i] != GY[i]) {
        REP(r, 4) {
            int nx = X[i] + dxs[r];
            int ny = Y[i] + dys[r];
            if(valid(nx, WIDTH) && valid(ny, HEIGHT) && !grid[ny][nx]) {
            } else {
                res++;
            }
        }
    }
    return res;
}

struct State{
    State* prev;
    int X[C], Y[C];
    int score;
    int near;
    void set_score(int turn) {
        score = calc_score(this->X, this->Y, turn);
        near = calc_near(this->X, this->Y);
    }
    bool operator < (const State& s) const {
        if(near != s.near) return near > s.near; // reversed
        return score > s.score; // reversed
    }
};

int zobrist_table[HEIGHT][WIDTH];
void init_zobrist() {
    REP(y, HEIGHT) REP(x, WIDTH) zobrist_table[y][x] = rand();
}

int zobrist_hash(const int X[C], const int Y[C]) {
    int h = 0;
    REP(i, C) h = h ^ zobrist_table[Y[i]][X[i]];
    return h;
}

State next_greedy(State* s, int next_turn) {
    State ns;
    ns.prev = s;
    bool grid[HEIGHT][WIDTH] = {};
    REP(i, C) grid[s->Y[i]][s->X[i]] = true;
    vector<int> perm(C);
    REP(i, C) perm[i] = i;
    random_shuffle(perm.begin(), perm.end());
    for(int i : perm) {
        ns.X[i] = s->X[i];
        ns.Y[i] = s->Y[i];
        const int dx = (ns.X[i] < GX[i] ? 1 : ns.X[i] > GX[i] ? -1 : 0);
        const int dy = (ns.Y[i] < GY[i] ? 1 : ns.Y[i] > GY[i] ? -1 : 0);
        bool okx = false;
        bool oky = false;
        if(dx != 0 && !grid[ns.Y[i]][ns.X[i] + dx]) {
            okx = true;
        }
        if(dy != 0 && !grid[ns.Y[i] + dy][ns.X[i]]) {
            oky = true;
        }
        if(okx && (!oky || rand() % 2 == 1)) {
            ns.X[i] += dx;
            grid[ns.Y[i]][ns.X[i]] = true;
        } else if(oky) {
            ns.Y[i] += dy;
            grid[ns.Y[i]][ns.X[i]] = true;
        }
    }
    ns.set_score(next_turn);
    return ns;
}

State next_greedy2(State* s, int next_turn) {
    State ns;
    ns.prev = s;
    bool grid[HEIGHT][WIDTH] = {};
    REP(i, C) grid[s->Y[i]][s->X[i]] = true;

    // vector<pair<int, int>> ps(C);
    // REP(i, C) ps[i] = make_pair(-abs(s->X[i] - GX[i])-abs(s->Y[i] - GY[i]), i);
    // sort(ps.begin(), ps.end());
    // for(auto p : ps) {
    vector<int> perm(C);
    REP(i, C) perm[i] = i;
    random_shuffle(perm.begin(), perm.end());
    for(int i : perm) {
        ns.X[i] = s->X[i];
        ns.Y[i] = s->Y[i];
        const int dx = (ns.X[i] < GX[i] ? 1 : ns.X[i] > GX[i] ? -1 : (rand() % 2 == 0 ? 1 : -1));
        const int dy = (ns.Y[i] < GY[i] ? 1 : ns.Y[i] > GY[i] ? -1 : (rand() % 2 == 0 ? 1 : -1));
        vector<int> perm;
        int rv = rand() % 2;
        perm.push_back(rv == 0 ? get_move(dx, 0) : get_move(0, dy));
        perm.push_back(rv == 1 ? get_move(dx, 0) : get_move(0, dy));
        perm.push_back(rv == 0 ? get_move(-dx, 0) : get_move(0, -dy));
        perm.push_back(rv == 1 ? get_move(-dx, 0) : get_move(0, -dy));
        for(int r : perm) if(r != 4) {
            if(valid(ns.X[i] + dxs[r], WIDTH) && valid(ns.Y[i] + dys[r], HEIGHT)) {
                if(!grid[ns.Y[i] + dys[r]][ns.X[i] + dxs[r]]) {
                    ns.X[i] += dxs[r];
                    ns.Y[i] += dys[r];
                    grid[ns.Y[i]][ns.X[i]] = true;
                    break;
                }
            }
        }
    }
    ns.set_score(next_turn);
    return ns;
}


const int MAX_TURN = 800;
const int BEAM_WIDTH = 4;
const int TRY_COUNT = 4;
vector<string> beam_search() {
    priority_queue<State> que[MAX_TURN];
    static State states[MAX_TURN][BEAM_WIDTH];
    int sc[MAX_TURN] = {};
    State first_state;
    REP(i, C) first_state.X[i] = SX[i];
    REP(i, C) first_state.Y[i] = SY[i];

    first_state.set_score(0);
    que[0].push(first_state);

    REP(i, MAX_TURN) {
        cerr << "turn " << i << endl;
        set<int> hashes;
        REP(j, BEAM_WIDTH) {
            if(que[i].empty()) break;

            const int h = zobrist_hash(que[i].top().X, que[i].top().Y);
            if(hashes.count(h)) {
                que[i].pop();
                continue;
            } else {
                hashes.insert(h);
            }
            cerr << sc[i] << endl;

            states[i][sc[i]++] = que[i].top(); que[i].pop();
            State* cur = &states[i][sc[i]-1];
            if(i + 1 < MAX_TURN) {
                REP(k, TRY_COUNT) {
                    State next = (i < MAX_TURN/2 ? next_greedy2(cur, i+1) : next_greedy2(cur, i+1));
                    que[i+1].push(next);
                }
            }
        }
    }
    State min_state = first_state;;
    int ans_turn = 0;
    REP(i, MAX_TURN) REP(j, sc[i]) {
        if(min_state.score > states[i][j].score) {
            min_state = states[i][j];
            ans_turn = i;
        }
    }
    vector<string> answers(ans_turn);
    State* cur = &min_state;
    for(int i = ans_turn-1; i >= 0; i--) {
        State* prev = cur->prev;
        for(int j = 0; j < C; j++) {
            answers[i] += string(1, move_to_char(get_move(cur->X[j] - prev->X[j], cur->Y[j] - prev->Y[j])));
        }
        cur = prev;
    }
    for(int i = 0; i < MAX_TURN; i++) {
        cerr << "score " << i << ": " << 1e9 / states[i][0].score << endl;
    }
    cerr << "best_score: " << 1e9 / min_state.score << endl;
    return answers;
};

void output(vector<string> answer) {
    cout << answer.size() << endl;
    for(int i = 0; i < answer.size(); i++) {
        cout << answer[i] << endl;
    }
}

int main(){
    iostream_init();
    init_zobrist();

    input();
    auto answer = beam_search();
    output(answer);

    return 0;
}

Submission Info

Submission Time
Task B - 日本橋大渋滞
User ichyo
Language C++14 (GCC 5.4.1)
Score 27210
Code Size 7327 Byte
Status AC
Exec Time 1440 ms
Memory 57472 KB

Judge Result

Set Name test_01 test_02 test_03 test_04 test_05 test_06 test_07 test_08 test_09 test_10 test_11 test_12 test_13 test_14 test_15 test_16 test_17 test_18 test_19 test_20 test_21 test_22 test_23 test_24 test_25 test_26 test_27 test_28 test_29 test_30
Score / Max Score 954 / 50000 991 / 50000 980 / 50000 901 / 50000 870 / 50000 957 / 50000 850 / 50000 990 / 50000 923 / 50000 927 / 50000 932 / 50000 934 / 50000 944 / 50000 891 / 50000 898 / 50000 941 / 50000 875 / 50000 916 / 50000 836 / 50000 863 / 50000 798 / 50000 962 / 50000 876 / 50000 842 / 50000 946 / 50000 917 / 50000 894 / 50000 865 / 50000 872 / 50000 865 / 50000
Status
AC × 1
AC × 1
AC × 1
AC × 1
AC × 1
AC × 1
AC × 1
AC × 1
AC × 1
AC × 1
AC × 1
AC × 1
AC × 1
AC × 1
AC × 1
AC × 1
AC × 1
AC × 1
AC × 1
AC × 1
AC × 1
AC × 1
AC × 1
AC × 1
AC × 1
AC × 1
AC × 1
AC × 1
AC × 1
AC × 1
Set Name Test Cases
test_01 subtask_01_01.txt
test_02 subtask_01_02.txt
test_03 subtask_01_03.txt
test_04 subtask_01_04.txt
test_05 subtask_01_05.txt
test_06 subtask_01_06.txt
test_07 subtask_01_07.txt
test_08 subtask_01_08.txt
test_09 subtask_01_09.txt
test_10 subtask_01_10.txt
test_11 subtask_01_11.txt
test_12 subtask_01_12.txt
test_13 subtask_01_13.txt
test_14 subtask_01_14.txt
test_15 subtask_01_15.txt
test_16 subtask_01_16.txt
test_17 subtask_01_17.txt
test_18 subtask_01_18.txt
test_19 subtask_01_19.txt
test_20 subtask_01_20.txt
test_21 subtask_01_21.txt
test_22 subtask_01_22.txt
test_23 subtask_01_23.txt
test_24 subtask_01_24.txt
test_25 subtask_01_25.txt
test_26 subtask_01_26.txt
test_27 subtask_01_27.txt
test_28 subtask_01_28.txt
test_29 subtask_01_29.txt
test_30 subtask_01_30.txt
Case Name Status Exec Time Memory
subtask_01_01.txt AC 1423 ms 57344 KB
subtask_01_02.txt AC 1412 ms 57216 KB
subtask_01_03.txt AC 1431 ms 57344 KB
subtask_01_04.txt AC 1416 ms 57344 KB
subtask_01_05.txt AC 1421 ms 57344 KB
subtask_01_06.txt AC 1414 ms 57344 KB
subtask_01_07.txt AC 1430 ms 57344 KB
subtask_01_08.txt AC 1416 ms 57344 KB
subtask_01_09.txt AC 1440 ms 57472 KB
subtask_01_10.txt AC 1412 ms 57344 KB
subtask_01_11.txt AC 1419 ms 57472 KB
subtask_01_12.txt AC 1438 ms 57472 KB
subtask_01_13.txt AC 1436 ms 57344 KB
subtask_01_14.txt AC 1421 ms 57344 KB
subtask_01_15.txt AC 1419 ms 57344 KB
subtask_01_16.txt AC 1411 ms 57344 KB
subtask_01_17.txt AC 1437 ms 57472 KB
subtask_01_18.txt AC 1437 ms 57472 KB
subtask_01_19.txt AC 1436 ms 57344 KB
subtask_01_20.txt AC 1427 ms 57472 KB
subtask_01_21.txt AC 1430 ms 57472 KB
subtask_01_22.txt AC 1410 ms 57344 KB
subtask_01_23.txt AC 1415 ms 57472 KB
subtask_01_24.txt AC 1415 ms 57472 KB
subtask_01_25.txt AC 1419 ms 57344 KB
subtask_01_26.txt AC 1418 ms 57344 KB
subtask_01_27.txt AC 1420 ms 57344 KB
subtask_01_28.txt AC 1415 ms 57472 KB
subtask_01_29.txt AC 1428 ms 57344 KB
subtask_01_30.txt AC 1418 ms 57344 KB