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 |
|
|
|
|
|
|
|
|
|
|
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 |