Submission #2141042


Source Code Expand

#define _CRT_SECURE_NO_WARNINGS
#include "bits/stdc++.h"
#include <random>
//#include <opencv2/core.hpp>    // coreモジュールのヘッダーをインクルード
//#include <opencv2/highgui.hpp> // highguiモジュールのヘッダーをインクルード
//#include <opencv2/imgproc.hpp>

//#define DEBUG
//#define VISUALIZE

#ifdef VISUALIZE
#include "visualizer.h"
#endif

using namespace std;

//呪文
#define DUMPOUT cerr
#define dump(...) DUMPOUT<<"  ";DUMPOUT<<#__VA_ARGS__<<" :["<<__LINE__<<":"<<__FUNCTION__<<"]"<<endl;DUMPOUT<<"    ";dump_func(__VA_ARGS__)

typedef unsigned uint; typedef long long ll; typedef unsigned long long ull; typedef pair<int, int> pii; typedef pair<ll, ll> pll; typedef pair<double, double> pdd; typedef pair<string, string> pss;
template <typename _KTy, typename _Ty> ostream& operator << (ostream& ostr, const pair<_KTy, _Ty>& m) { ostr << "{" << m.first << ", " << m.second << "}"; return ostr; }
template <typename _KTy, typename _Ty> ostream& operator << (ostream& ostr, const map<_KTy, _Ty>& m) { if (m.empty()) { ostr << "{ }"; return ostr; } ostr << "{" << *m.begin(); for (auto itr = ++m.begin(); itr != m.end(); itr++) { ostr << ", " << *itr; } ostr << "}"; return ostr; }
template <typename _Ty> ostream& operator << (ostream& ostr, const vector<_Ty>& v) { if (v.empty()) { ostr << "{ }"; return ostr; } ostr << "{" << v.front(); for (auto itr = ++v.begin(); itr != v.end(); itr++) { ostr << ", " << *itr; }	ostr << "}"; return ostr; }
template <typename _Ty> ostream& operator << (ostream& ostr, const set<_Ty>& s) { if (s.empty()) { ostr << "{ }"; return ostr; } ostr << "{" << *(s.begin()); for (auto itr = ++s.begin(); itr != s.end(); itr++) { ostr << ", " << *itr; }	ostr << "}"; return ostr; }
template <typename _Ty> ostream& operator << (ostream& ostr, const stack<_Ty>& s) { if (s.empty()) { ostr << "{ }"; return ostr; } stack<_Ty> t(s); ostr << "{" << t.top(); t.pop(); while (!t.empty()) { ostr << ", " << t.top(); t.pop(); } ostr << "}";	return ostr; }
template <typename _Ty> ostream& operator << (ostream& ostr, const list<_Ty>& l) { if (l.empty()) { ostr << "{ }"; return ostr; } ostr << "{" << l.front(); for (auto itr = ++l.begin(); itr != l.end(); ++itr) { ostr << ", " << *itr; } ostr << "}"; return ostr; }
template <typename _KTy, typename _Ty> istream& operator >> (istream& istr, pair<_KTy, _Ty>& m) { istr >> m.first >> m.second; return istr; }
template <typename _Ty> istream& operator >> (istream& istr, vector<_Ty>& v) { for (size_t i = 0; i < v.size(); i++) istr >> v[i]; return istr; }
namespace aux { // print tuple
	template<typename Ty, unsigned N, unsigned L> struct tp { static void print(ostream& os, const Ty& v) { os << get<N>(v) << ", "; tp<Ty, N + 1, L>::print(os, v); } };
	template<typename Ty, unsigned N> struct tp<Ty, N, N> { static void print(ostream& os, const Ty& value) { os << get<N>(value); } };
}
template<typename... Tys> ostream& operator<<(ostream& os, const tuple<Tys...>& t) { os << "{"; aux::tp<tuple<Tys...>, 0, sizeof...(Tys)-1>::print(os, t); os << "}"; return os; }

template<typename A, size_t N, typename T> inline void Fill(A(&array)[N], const T &val) { std::fill((T*)array, (T*)(array + N), val); }

void dump_func() { DUMPOUT << endl; }
template <class Head, class... Tail> void dump_func(Head&& head, Tail&&... tail) { DUMPOUT << head; if (sizeof...(Tail) == 0) { DUMPOUT << " "; } else { DUMPOUT << ", "; } dump_func(std::move(tail)...); }

#define PI 3.14159265358979323846
#define EPS 1e-11
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n)  FOR(i,0,n)
#define all(x) (x).begin(), (x).end()
#define SZ(x) ((int)(x).size())
#define fake false



unsigned w;

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

#ifdef VISUALIZE
visualizer vis;
#endif

class chokudai001 {

	int di[4] = { 0, -1, 0, 1 };
	int dj[4] = { 1, 0, -1, 0 };

public:

	typedef vector<int> Path;
	typedef vector<Path> Paths;
	typedef pair<Paths, vector<bool>> State;
	typedef priority_queue<pair<int, State>, vector<pair<int, State>>, greater<pair<int, State>>> PQ;

	vector<int> A;
	int N;
	int total;
	int step;

	chokudai001() {}

	void init(int N);
	void init_random(int N, int M);

	int getVal(int i, int j);
	int getVal(pii p);
	void decrement(int p);

	Paths beam_search(int width);
	int calc_score(const Path& path);
	int calc_score(const State& paths);

	void output_moves(const Path& path);
	void output_moves();

	void visualize(int waitTime);
};

chokudai001::Paths chokudai001::beam_search(int width = 100) {

	int highest = -1;
	REP(i, N) REP(j, N) highest = max(highest, getVal(i, j));

	vector<State> initial_state;
	REP(i, N) REP(j, N) if (getVal(i, j) == highest) {
		vector<bool> used(N * N, false);
		used[i * N + j] = true;
		initial_state.push_back(pair<Paths, vector<bool>>(Paths({ { i * N + j } }), used));
	}

	PQ pq;
	for (int i = 0; i < initial_state.size(); i++) {
		pq.push(pair<int, State>(calc_score(initial_state[i]), initial_state[i]));
	}

	for (int k = 1; k < N * N; k++) {

		PQ pq_new;
		while (!pq.empty()) {
			State state = pq.top().second; pq.pop();
			//dump(state);
			Paths& paths = state.first;
			vector<bool>& used = state.second;
			Path& path = paths.back();
			int p = path.back();
			int i = p / N, j = p % N;

			bool update = false;
			// 4-dir
			{
				vector<int> pCandidate;
				for (int d = 0; d < 4; d++) {
					int ni = i + di[d], nj = j + dj[d];
					if (ni < 0 || N <= ni || nj < 0 || N <= nj) continue;
					if (used[ni * N + nj]) continue;

					update = true;
					pCandidate.push_back(ni * N + nj);
				}
				if (update) {
					int pSelected = pCandidate[xor128() % pCandidate.size()];
					path.push_back(pSelected);
					used[pSelected] = true;
					pq_new.push(pair<int, State>(calc_score(state), state));
					path.pop_back();
					used[pSelected] = false;
				}
			}
			// new seed
			if (!update) {
				int highest_tmp = -1;
				REP(p, N * N) {
					if (used[p]) continue;
					highest_tmp = max(highest_tmp, A[p]);
				}
				vector<int> pCandidate;
				REP(p, N * N) {
					if (used[p]) continue;
					if (A[p] == highest_tmp) pCandidate.push_back(p);
				}

				int pSelected = pCandidate[xor128() % pCandidate.size()];

				paths.push_back(Path({ pSelected }));
				used[pSelected] = true;
				pq_new.push(pair<int, State>(calc_score(state), state));
				paths.pop_back();
				used[pSelected] = false;
			}
		}
		while (pq_new.size() > width) pq_new.pop();
		pq = pq_new;
	}

	//dump(pq.top().second.first.size(), pq.top());

	return pq.top().second.first;
}

void chokudai001::output_moves() {
	Paths paths = beam_search();

	for (int i = 0; i < paths.size(); i++) {
		output_moves(paths[i]);
#ifdef VISUALIZE
		vis.draw(A, step, total, 300);
#endif
	}
}

void chokudai001::output_moves(const Path& path) {
	
	for (int k = path.size() - 1; k >= 1; k--) {
		while (A[path[k - 1]] <= A[path[k]]) {
			decrement(path[k]);
			for (int l = k + 1; l < path.size(); l++) {
				int x = A[path[l - 1]];
				int y = A[path[l]];
				if (x != y || y == 0) break;
				decrement(path[l]);
			}
			step++;
		}
	}

	{
		int k = 0;
		while (A[path[k]] > 0) {
			decrement(path[k]);
			for (int l = k + 1; l < path.size(); l++) {
				int x = A[path[l - 1]];
				int y = A[path[l]];
				if (x != y || y == 0) break;
				decrement(path[l]);
			}
			step++;
		}
	}
}

int chokudai001::calc_score(const State& state) {
	const Paths& paths = state.first;
	//int score = paths.size() * 100;
	int score = 0;
	for (int i = 0; i < paths.size(); i++) {
		score += calc_score(paths[i]);
	}
	return score;
}

int chokudai001::calc_score(const Path& path) {
	int score = 0;
	score += A[path[0]];
	for (int i = 0; i < path.size() - 1; i++) {
		int x = A[path[i]];
		int y = A[path[i + 1]];
		if (x <= y) score += y - x + 1;
	}
	return score;
}

void chokudai001::init(int N) {

	A.resize(N * N, 0);
	REP(i, N) REP(j, N) {
		cin >> A[i * N + j];
		total += A[i * N + j];
	}

	this->N = N;
	this->step = 0;
}

void chokudai001::init_random(int N, int M) {

	A.resize(N * N, 0);
	REP(i, N) REP(j, N) {
		int a = xor128() % M + 1;
		A[i * N + j] = a;
		total += a;
	}

	this->N = N;
	this->step = 0;

}

int chokudai001::getVal(int i, int j) {
	return A[i * N + j];
}

int chokudai001::getVal(pii p) {
	return A[p.first * N + p.second];
}


void chokudai001::decrement(int p) {
	A[p]--; total--;
#ifndef DEBUG
	int i = p / N, j = p % N;
	printf("%d %d\n", i + 1, j + 1);
#endif
}

void chokudai001::visualize(int waitTime) {
#ifdef VISUALIZE
	vis.draw(A, step, total, waitTime);
#endif
}


int main()
{
#ifdef DEBUG
	clock_t start, end;
	start = clock();
#endif

	cin.tie(0);
	ios::sync_with_stdio(false);

	//random_device rnd;
	//mt19937 mt(rnd());
	//w = mt();
	w = 1234567;

	const int N = 30;
	const int M = 100;
	chokudai001 c001;

#ifdef DEBUG
	c001.init_random(N, M);
	//c001.init(N);
#else
	c001.init(N);
#endif

#ifdef VISUALIZE
	vis = visualizer(N, c001.A);
#endif


	c001.output_moves();


#ifdef VISUALIZE
	vis.draw(c001.A, c001.step, c001.total, 0);
#endif

#ifdef DEBUG
	end = clock();
	printf("%d msec.\n", end - start);
#endif
	return 0;
}

Submission Info

Submission Time
Task A - 高橋君の山崩しゲーム
User komori3
Language C++14 (GCC 5.4.1)
Score 811297
Code Size 9594 Byte
Status AC
Exec Time 113 ms
Memory 768 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
Score / Max Score 81367 / 100000 80704 / 100000 81448 / 100000 80791 / 100000 81612 / 100000 80837 / 100000 81354 / 100000 81242 / 100000 80865 / 100000 81077 / 100000
Status
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
Case Name Status Exec Time Memory
subtask_01_01.txt AC 91 ms 640 KB
subtask_01_02.txt AC 90 ms 640 KB
subtask_01_03.txt AC 50 ms 640 KB
subtask_01_04.txt AC 92 ms 768 KB
subtask_01_05.txt AC 91 ms 640 KB
subtask_01_06.txt AC 113 ms 768 KB
subtask_01_07.txt AC 74 ms 640 KB
subtask_01_08.txt AC 66 ms 640 KB
subtask_01_09.txt AC 89 ms 640 KB
subtask_01_10.txt AC 75 ms 640 KB