Submission #2078990

---

Source Code Expand

#include <bits/stdc++.h>
#define rep(i,n) for(int i=0;i<(n);++i)
#define ALL(A) A.begin(), A.end()
#define INF 1<<28

using namespace std;

typedef long long ll;
typedef pair<int, int> P;
const int MAX_N = 2001;
const int MAX_H = 50;
const int MAX_W = 50;

const string dir = "URDL";
const int dr[4] = {-1, 0, 1, 0};
const int dc[4] = { 0, 1, 0,-1};

int H, W, K, sr, sc;
int N;
int fr[MAX_N], fc[MAX_N], F[MAX_N], D[MAX_N];
vector<string> grid;

int toFood[MAX_N];		// 犬の位置から各フードの位置までの距離
int dist[MAX_N][MAX_N];	// 各フード間の距離
int visit[MAX_H][MAX_W];		// 訪問フラグ


#if SUBMIT
const int64_t CYCLES_PER_SEC = 2800000000;
#else
const int64_t CYCLES_PER_SEC = 2400000000;
#endif

const double TIME_LIMIT = 9.5;
const int MAX_V = 200;
const int MAX_HASH_SIZE = 5*(int)1e7;
const int MAX_BEAM_DEPTH = 200;
const int MAX_BEAM_WIDTH = 100;

struct Timer {
	int64_t start;
	int counter;
	double t;

	Timer() {
		reset();
	}

	void plus(double a){
		start -= a * CYCLES_PER_SEC;
	}

	int64_t getCycle() {
		uint32_t low, high;
		__asm__ volatile ("rdtsc" : "=a" (low), "=d" (high));
		return ((int64_t)low) | ((int64_t)high << 32);
	}

	void reset(){
		counter = 0;
		start = getCycle();
		t = 0.0;
	}

	double get(){
		return t = (double)(getCycle() - start) / CYCLES_PER_SEC;
	}
};

unsigned Rand(){ 
	static unsigned x=123456789;
	static unsigned y=362436069;
	static unsigned z=521288629;
	static unsigned w=88675123; 
	unsigned t=x^(x<<11);
	x=y; y=z; z=w;
 
	return w=(w^(w>>19))^(t^(t>>8));
}

struct NODE{
	int score;
	vector<int> perm;
	NODE(int _score, vector<int> _perm):score(_score),perm(_perm){}
	
	bool operator>(const NODE& node) const{
		return score > node.score;
	}
};

namespace Pool{
	int Q_size[MAX_BEAM_DEPTH + 1];
	NODE* Q[MAX_BEAM_DEPTH + 1][MAX_BEAM_WIDTH * MAX_BEAM_WIDTH];

	void initQueue(int sz){
		for (int i = 0; i < sz; ++i) Q_size[i] = 0;
	}

	void pushQ(int i, NODE* x){
		Q[i][Q_size[i]++] = x;
	}
};

struct NODECompare{
	bool operator()(NODE* n1, NODE* n2) const{
		return *n1 > *n2;
	}
};


bool table[MAX_HASH_SIZE];

void calcDist(int cr, int cc){
	memset(visit, -1, sizeof(visit));
	queue<P> que;
	que.push(P(cr * W + cc, 0));
	while(!que.empty()){
		P curr = que.front(); que.pop();
		cr = curr.first / W;
		cc = curr.first % W;
		int d = curr.second;
		if (visit[cr][cc] == -1){
			visit[cr][cc] = d;
			rep (k, 4){
				int nr = cr + dr[k];
				int nc = cc + dc[k];
				if (nr < 0 || nr >= H || nc < 0 || nc >= W) continue;
				if (grid[nr][nc] == '#') continue;
				if (visit[nr][nc] == -1){
					que.push(P(nr * W + nc, d + 1));
				} // end if
			} // end rep
		} // end if
	}
}	

void calctoFood(void){
	calcDist(sr, sc);
	rep (i, N){
		toFood[i] = visit[fr[i]][fc[i]];
	} // end rep
}			

void calcF2F(void){
	rep (i, N){
		calcDist(fr[i], fc[i]);
		rep (j, N){
			dist[i][j] = visit[fr[j]][fc[j]];
		} // end rep
	} // end rep
}

void disp_grid(void){
	rep (i, H){
		rep (j, W){
			cerr << grid[i][j];
		} // end rep
		cerr << endl;
	} // end rep
}

void dispVisit(void){
	rep (i, H){
		rep (j, W){
			cerr << setw(2) << visit[i][j];
		} // end rep
		cerr << endl;
	} // end rep
}

class BeamSearch{
public:
	Timer timer;
 	double startTime;
	double endTime;
	double currentTime;

	vector<int> hillClimbing(void){
		startTime = timer.t;
		endTime = TIME_LIMIT;
		initZobrit();
		vector<int> perm = init_perm();
		vector<int> best = perm;
		int bestScore = calcScore(perm);
		int iter = 0;
		while((currentTime = timer.get()) < endTime){
			int i = Rand() % N;
			int j = Rand() % (N - 1);
			if (j == i) ++j;
			swap(perm[i], perm[j]);
			int h = hash(perm);
			if (table[h]){
				swap(perm[i], perm[j]);
				continue;
			} // end if
			table[h] |= true;
			int score = calcScore(perm);
			if (bestScore < score){
				bestScore = score;
				best = perm;
			}else{
				swap(perm[i], perm[j]);
			} // end if
		} // end while
		return best;
	}

	vector<int> beam(void){
		startTime = timer.t;
		endTime = TIME_LIMIT;
		initZobrit();
		Pool::initQueue(MAX_BEAM_DEPTH + 1);
		int bestScore = 0;
		vector<int> best; best.clear();
		rep (i, MAX_BEAM_WIDTH){
			vector<int> curr = init_perm();
			int score = calcScore(curr);
			if (score == -1) continue;
			int h = hash(curr);
			if (table[h]){
				continue;
			} // end if
			table[h] |= true;
			NODE* origin = new NODE(score, curr);
			if (score > bestScore){
				bestScore = score;
				best = curr;
			} // end if
		} // end rep

		int lim = MAX_BEAM_WIDTH;
		int iter = 0;		
		for (int step = 0; step < MAX_BEAM_DEPTH; ++step){
			++iter;
			if (Pool::Q_size[step] == 0) break;
			sort(Pool::Q[step],Pool::Q[step] + Pool::Q_size[step], NODECompare());
			
			if ((currentTime = timer.get()) >= endTime){
				break;
			} // end if

			int lookUpSize = min(Pool::Q_size[step], lim);
			for (int qIdx = 0; qIdx < lookUpSize; ++qIdx){
				if ((currentTime = timer.get()) >= endTime){
					break;
				} // end if
				auto q = Pool::Q[step][qIdx];
				for (int next = 0; next < lim; ++next){
					int score = q->score;
					vector<int> perm = q->perm;
					int from = Rand() % N;
					int   to = Rand() % (N - 1);
					if (from == to) ++to;
					swap(perm[from], perm[to]);
					int h = hash(perm);
					if (table[h]) continue;
					table[h] |= true;
					int nextScore = calcScore(perm);
					NODE* cand = new NODE(nextScore, perm);
					if (bestScore < nextScore){
						bestScore = nextScore;
						best = perm;
					} // end if
					Pool::pushQ(step + 1, cand);
					if ((currentTime = timer.get()) >= endTime){
						break;
					} // end if
				} // end for
			} // end for
		} // end for
		cerr << "iter: " << iter << ' ';

		return best;
	}

private:
	vector<int> random_table;

	int calcScore(vector<int> perm){
		int sumt = 0;
		int score = 0;
		int t = toFood[perm[0]];
		if (t == -1){
			return -1;
		} // end if
		sumt += t;
		score += max(0, F[perm[0]] - sumt * D[perm[0]]);
		for (int i = 1; i < N; ++i){
			int t = dist[perm[i-1]][perm[i]];
			if (t == -1){
				return -1;
			} // end if
			sumt += t;
			score += max(0, F[perm[i]] - sumt * D[perm[i]]);
		} // end for
		return score; 
	}

	vector<int> init_perm(void){
		vector<int> perm(N, 0);
		rep (i, N) perm[i] = i;
		for (int i = 0; i < N - 1; ++i){
			int j = Rand() % (N - i) + i;
			swap (perm[i], perm[j]);
		} // end for
		return perm;
	}

	void initZobrit(void){
		random_table.clear();
		random_table.resize(N*N, 0);
		for (int i = 0; i < N*N; ++i) random_table[i] = Rand() % MAX_HASH_SIZE;
	}

	int hash(vector<int> perm){
		int h = 0;
		for (int i = 0; i < N; ++i){
			h = h ^ random_table[i + N * perm[i]];
		} // end for
		return h % MAX_HASH_SIZE;
	}
};

string from2to(int spos, int epos){
	string res = "";
	int cr = epos / W;
	int cc = epos % W;
	while(cr * W + cc != spos){
		int curr = visit[cr][cc];
		for (int k = 0; k < 4; ++k){
			int nr = cr + dr[k];
			int nc = cc + dc[k];
			if (nr < 0 || nr >= H || nc < 0 || nc >= W) continue;
			if (visit[nr][nc] == -1) continue;
			if (visit[nr][nc] + 1 == curr){
				res += dir[(k + 2) % 4];
				cr = nr;
				cc = nc;
				break;
			} // end if
		} // end for
	} // end while
	reverse(ALL(res));

	return res;
}

int main()
{
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	memset(fr, 0, sizeof(fr));
	memset(fc, 0, sizeof(fc));
	memset(F, 0, sizeof(F));
	memset(D, 0, sizeof(D));
	memset(toFood, -1, sizeof(toFood));
	memset(dist, -1, sizeof(dist));
	grid.clear();
	cin >> H >> W >> K >> sr >> sc;
	--sr;
	--sc;
	grid.resize(H, string(W, '.'));
	rep (i, H){
		cin >> grid[i];
	} // end rep

	cin >> N;
	rep (i, N){
		cin >> fr[i] >> fc[i] >> F[i] >> D[i];
		--fr[i];
		--fc[i];
//		grid[fr[i]][fc[i]] = (char)('0' + i);
	} // end rep

//	grid[sr][sc] = 'S';

#if DEBUG	
	disp_grid();
#endif
	calctoFood();

#if DEBUG
	rep (i, N){
		cerr << toFood[i] << ' ';
	} //end rep
	cerr << endl;
#endif
	calcF2F();
#if DEBUG
	rep (i, N){
		rep (j, N){
			cerr << dist[i][j] << ' ';
		} // end rep
		cerr << endl;
	} // end rep
#endif
	BeamSearch BS;
//	vector<int> res = BS.beam();
	vector<int> res = BS.hillClimbing();

#if DEBUG
	rep (i, (int)res.size()){
		cerr << res[i] << ' ';
	} // end rep
	cerr << endl;
#endif
	calctoFood();
	string ans = "";
#if DEBUG
	dispVisit();
#endif
	string curr = from2to(sr * W + sc, fr[res[0]] * W + fc[res[0]]);
	ans += curr;

	for (int i = 0; i < (int)res.size() - 1; ++i){
		calcDist(fr[res[i]], fc[res[i]]);
		string curr = from2to(fr[res[i]] * W + fc[res[i]], fr[res[i+1]] * W + fc[res[i+1]]);
		ans += curr;
	} // end for


	if (ans.length() > K){
		ans = ans.substr(0, K);
	}else{
		while(ans.length() < K){
			ans += '-';
		} // end while
	} // end if

	cout << ans << endl;

	return 0;
}

Submission Info

Judge Result