Submission #1173881
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);
}
struct State{
State* prev;
int X[C], Y[C];
int score;
void set_score(int turn) {
score = calc_score(this->X, this->Y, turn);
}
bool operator < (const State& s) const {
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 : 0);
const int dy = (ns.Y[i] < GY[i] ? 1 : ns.Y[i] > GY[i] ? -1 : 0);
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 = 200;
const int BEAM_WIDTH = 10;
const int TRY_COUNT = 10;
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 |
5763 |
Code Size |
6704 Byte |
Status |
AC |
Exec Time |
1799 ms |
Memory |
80528 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 |
202 / 50000 |
209 / 50000 |
195 / 50000 |
211 / 50000 |
207 / 50000 |
198 / 50000 |
184 / 50000 |
197 / 50000 |
193 / 50000 |
182 / 50000 |
201 / 50000 |
206 / 50000 |
185 / 50000 |
194 / 50000 |
166 / 50000 |
206 / 50000 |
179 / 50000 |
183 / 50000 |
179 / 50000 |
179 / 50000 |
206 / 50000 |
191 / 50000 |
184 / 50000 |
178 / 50000 |
188 / 50000 |
194 / 50000 |
223 / 50000 |
173 / 50000 |
182 / 50000 |
188 / 50000 |
Status |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
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 |
1780 ms |
78228 KB |
subtask_01_02.txt |
AC |
1761 ms |
78196 KB |
subtask_01_03.txt |
AC |
1763 ms |
78228 KB |
subtask_01_04.txt |
AC |
1765 ms |
78260 KB |
subtask_01_05.txt |
AC |
1764 ms |
78196 KB |
subtask_01_06.txt |
AC |
1766 ms |
78100 KB |
subtask_01_07.txt |
AC |
1795 ms |
80528 KB |
subtask_01_08.txt |
AC |
1765 ms |
78196 KB |
subtask_01_09.txt |
AC |
1777 ms |
78196 KB |
subtask_01_10.txt |
AC |
1769 ms |
78100 KB |
subtask_01_11.txt |
AC |
1755 ms |
78228 KB |
subtask_01_12.txt |
AC |
1768 ms |
78228 KB |
subtask_01_13.txt |
AC |
1794 ms |
78164 KB |
subtask_01_14.txt |
AC |
1763 ms |
78164 KB |
subtask_01_15.txt |
AC |
1799 ms |
78100 KB |
subtask_01_16.txt |
AC |
1765 ms |
80364 KB |
subtask_01_17.txt |
AC |
1777 ms |
78132 KB |
subtask_01_18.txt |
AC |
1797 ms |
78132 KB |
subtask_01_19.txt |
AC |
1768 ms |
78228 KB |
subtask_01_20.txt |
AC |
1770 ms |
78228 KB |
subtask_01_21.txt |
AC |
1755 ms |
78196 KB |
subtask_01_22.txt |
AC |
1781 ms |
78196 KB |
subtask_01_23.txt |
AC |
1775 ms |
78100 KB |
subtask_01_24.txt |
AC |
1776 ms |
78196 KB |
subtask_01_25.txt |
AC |
1772 ms |
80528 KB |
subtask_01_26.txt |
AC |
1778 ms |
78196 KB |
subtask_01_27.txt |
AC |
1756 ms |
78164 KB |
subtask_01_28.txt |
AC |
1778 ms |
78196 KB |
subtask_01_29.txt |
AC |
1787 ms |
78164 KB |
subtask_01_30.txt |
AC |
1793 ms |
78132 KB |