Submission #1173667
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
}
};
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());
REP(i, C) {
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);
if(dx != 0 && !grid[ns.Y[i]][ns.X[i] + dx]) {
ns.X[i] += dx;
grid[ns.Y[i]][ns.X[i]] = true;
} else if(dy != 0 && !grid[ns.Y[i] + dy][ns.X[i]]) {
ns.Y[i] += dy;
grid[ns.Y[i]][ns.X[i]] = true;
}
}
ns.set_score(next_turn);
return ns;
}
const int MAX_TURN = 100;
const int BEAM_WIDTH = 50;
const int TRY_COUNT = 50;
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;
REP(j, BEAM_WIDTH) {
if(que[i].empty()) break;
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 = next_greedy(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();
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 |
4619 |
Code Size |
4393 Byte |
Status |
AC |
Exec Time |
3960 ms |
Memory |
1000204 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 |
159 / 50000 |
160 / 50000 |
157 / 50000 |
159 / 50000 |
172 / 50000 |
159 / 50000 |
153 / 50000 |
160 / 50000 |
147 / 50000 |
151 / 50000 |
156 / 50000 |
156 / 50000 |
149 / 50000 |
161 / 50000 |
148 / 50000 |
161 / 50000 |
154 / 50000 |
149 / 50000 |
149 / 50000 |
152 / 50000 |
163 / 50000 |
153 / 50000 |
154 / 50000 |
145 / 50000 |
143 / 50000 |
154 / 50000 |
155 / 50000 |
142 / 50000 |
149 / 50000 |
149 / 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 |
3764 ms |
998284 KB |
subtask_01_02.txt |
AC |
3801 ms |
994444 KB |
subtask_01_03.txt |
AC |
3834 ms |
991372 KB |
subtask_01_04.txt |
AC |
3780 ms |
992780 KB |
subtask_01_05.txt |
AC |
3767 ms |
992396 KB |
subtask_01_06.txt |
AC |
3815 ms |
996620 KB |
subtask_01_07.txt |
AC |
3856 ms |
993164 KB |
subtask_01_08.txt |
AC |
3749 ms |
995852 KB |
subtask_01_09.txt |
AC |
3801 ms |
996108 KB |
subtask_01_10.txt |
AC |
3803 ms |
995724 KB |
subtask_01_11.txt |
AC |
3825 ms |
997132 KB |
subtask_01_12.txt |
AC |
3837 ms |
992396 KB |
subtask_01_13.txt |
AC |
3827 ms |
994324 KB |
subtask_01_14.txt |
AC |
3794 ms |
997388 KB |
subtask_01_15.txt |
AC |
3925 ms |
1000204 KB |
subtask_01_16.txt |
AC |
3872 ms |
997900 KB |
subtask_01_17.txt |
AC |
3823 ms |
1000204 KB |
subtask_01_18.txt |
AC |
3900 ms |
993932 KB |
subtask_01_19.txt |
AC |
3960 ms |
994316 KB |
subtask_01_20.txt |
AC |
3880 ms |
998668 KB |
subtask_01_21.txt |
AC |
3809 ms |
997388 KB |
subtask_01_22.txt |
AC |
3787 ms |
992908 KB |
subtask_01_23.txt |
AC |
3859 ms |
990348 KB |
subtask_01_24.txt |
AC |
3918 ms |
992268 KB |
subtask_01_25.txt |
AC |
3771 ms |
992652 KB |
subtask_01_26.txt |
AC |
3822 ms |
997772 KB |
subtask_01_27.txt |
AC |
3865 ms |
992012 KB |
subtask_01_28.txt |
AC |
3932 ms |
996108 KB |
subtask_01_29.txt |
AC |
3889 ms |
994700 KB |
subtask_01_30.txt |
AC |
3850 ms |
992908 KB |