Submission #1604872
Source Code Expand
//#define __USE_MINGW_ANSI_STDIO 0
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<int> VI;
typedef vector<VI> VVI;
typedef vector<ll> VL;
typedef vector<VL> VVL;
typedef pair<int, int> PII;
#define FOR(i, a, n) for (ll i = (ll)a; i < (ll)n; ++i)
#define REP(i, n) FOR(i, 0, n)
#define ALL(x) x.begin(), x.end()
#define IN(a, b, x) (a<=x&&x<b)
#define MP make_pair
#define PB push_back
const int INF = (1LL<<30);
const ll LLINF = (1LL<<60);
const double PI = 3.14159265359;
const double EPS = 1e-12;
const int MOD = 1000000007;
//#define int ll
template <typename T> T &chmin(T &a, const T &b) { return a = min(a, b); }
template <typename T> T &chmax(T &a, const T &b) { return a = max(a, b); }
int dx[] = {0, 1, 0, -1}, dy[] = {1, 0, -1, 0};
#define MAIN
const int h = 30, w = 30;
int board[30][30], bo[30][30];
bool used[30][30];
int sum, retsum;
double eval(vector<PII> v) {
// 連続列vから評価値を求める
// 評価が高いものほど評価値を高くする
if(v.size() == 0) return INF;
VI vec;
int szlim = INF;
REP(i, v.size()) {
vec.PB(board[v[i].first][v[i].second]);
chmin(szlim, (int)i+vec[i]);
if(i!=v.size()-1 && v[i] == v[v.size()-1]) return INF;
}
//連続列の長さ制限をする
if(szlim < (int)vec.size()) return INF;
int mi = INF;
REP(i, vec.size()) chmin(mi, vec[i]-((int)vec.size()-1-(int)i));
sum = 0, retsum = 0;
REP(i, vec.size()) sum += vec[i] - (mi + vec.size()-1-i), retsum += vec[i];
sum += mi + vec.size()-1;
return (double)sum/retsum;
}
vector<PII> func(int sx, int sy) {
vector<PII> ret;
ret.PB({sy, sx});
// ビーム幅k
int k = 2;
double retval = INF;
queue<vector<PII>> que;
que.push({{sy, sx}});
while(que.size()) {
// 連続列とその評価値
priority_queue<pair<vector<PII>, double>> pq;
while(que.size()) {
vector<PII> v = que.front(); que.pop();
int x = v[v.size()-1].second, y = v[v.size()-1].first;
REP(i, 4) {
int nx = x + dx[i], ny = y + dy[i];
if(!IN(0, w, nx) || !IN(0, h, ny)) continue;
// vにnx, nyを付け加えてその連続列について評価
vector<PII> tmp = v;
tmp.PB(MP(ny, nx));
double val = eval(tmp);
if(val == INF) continue;
if(val < retval) {
ret = tmp, retval = val;
}
pq.push(MP(tmp, val));
}
}
// cout << retval << " ";
// if(pq.size()) cout << pq.top().second << endl;
// else cout << endl;
int cnt = 0;
while(pq.size()) {
que.push(pq.top().first);
pq.pop();
cnt++;
if(cnt >= k) break;
}
}
return ret;
}
signed main(void)
{
REP(i, h) REP(j, w) cin >> board[i][j];
vector<PII> ans;
int score = 0, prev = 0;
int cnt = 0;
int size = 0, times = 0;
bool update = true;
while(update) {
// 長さが大きいものを優先的に選ぶ
// 最初の方に使う
int ma = 0;
REP(i, h) REP(j, w) chmax(ma, board[i][j]);
if(!ma) break;
vector<PII> v;
double vval = eval(v);
REP(i, h) REP(j, w) {
// cout << "i:" << i << " j:" << j << " " << vval << " " << v.size() << endl;
vector<PII> tmp = func(j, i);
if(eval(tmp) < vval) {
v = tmp, vval = eval(v);
}
}
times++, size += v.size();
eval(v);
// cout << "val:" << vval << " sum:" << sum << " retsum:" << retsum << endl;
// for(PII i: v) cout << i.first << "," << i.second << " "; cout << endl;
// for(PII i: v) cout << board[i.first][i.second] << " "; cout << endl;
// cout << size << " " << v.size() << " ";
// vを追っていって連続列をつくる
FOR(i, 1, v.size()) {
while(board[v[i].first][v[i].second] > 0
&& board[v[i].first][v[i].second] > board[v[i-1].first][v[i-1].second]-1) {
board[v[i].first][v[i].second]--;
ans.PB({v[i].first, v[i].second});
score++;
}
}
for(int i=v.size()-1; i>=0; --i) {
if(board[v[i].first][v[i].second] == 0) v.pop_back();
else break;
}
if(v.size() == 1) {
while(board[v[0].first][v[0].second]) {
board[v[0].first][v[0].second]--;
ans.PB({v[0].first, v[0].second});
score++;
}
// cout << score << " " << score-prev << endl;
prev = score;
continue;
}
bool endf = false;
while(1) {
// (sy, sx)からはじめて条件を満たすところまで1手番で操作する
int len = 0;
REP(i, v.size()-1) {
board[v[i].first][v[i].second]--;
ans.PB({v[i].first, v[i].second});
if(board[v[i+1].first][v[i+1].second] == 0
|| board[v[i].first][v[i].second] != board[v[i+1].first][v[i+1].second]) {
len = i;
break;
}
}
if(len == 0 && v.size() >= 2
&& board[v[v.size()-2].first][v[v.size()-2].second]
== board[v[v.size()-1].first][v[v.size()-1].second]
&& board[v[v.size()-1].first][v[v.size()-1].second]) {
//v.size()-1にも操作できる
board[v[v.size()-1].first][v[v.size()-1].second]--;
ans.PB({v[v.size()-1].first, v[v.size()-1].second});
len = v.size()-1;
}
if(endf && len == 0) break;
if(len != 0) endf = true;
score++;
}
// cout << score << " " << score-prev << " " << (score-prev)/v.size() << endl;
prev = score;
cnt++;
// cout << "----------------------" << endl;
// REP(i, h) {
// REP(j, w) {
// cout << board[i][j] << " ";
// }
// cout << endl;
// }
}
// cout << "end" << endl;
REP(i, h) {
REP(j, w) {
while(board[i][j]) board[i][j]--, ans.PB({i, j}), score++;
}
}
#ifdef MAIN
for(PII i: ans) cout << i.first+1 << " " << i.second+1 << endl;
#else
// for(int i: vv) cout << i << " "; cout << endl;
cout << "score:" << 100000 - score << " " << ans.size() << endl;
cout << size << " " << times << " " << size/times << endl;
#endif
return 0;
}
Submission Info
Submission Time |
|
Task |
A - 高橋君の山崩しゲーム |
User |
ferin_tech |
Language |
C++14 (GCC 5.4.1) |
Score |
787405 |
Code Size |
6231 Byte |
Status |
AC |
Exec Time |
5055 ms |
Memory |
1016 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 |
79427 / 100000 |
78256 / 100000 |
78966 / 100000 |
78420 / 100000 |
78778 / 100000 |
78315 / 100000 |
79023 / 100000 |
79125 / 100000 |
78587 / 100000 |
78508 / 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 |
4168 ms |
1016 KB |
subtask_01_02.txt |
AC |
3884 ms |
1016 KB |
subtask_01_03.txt |
AC |
4355 ms |
1016 KB |
subtask_01_04.txt |
AC |
4747 ms |
1016 KB |
subtask_01_05.txt |
AC |
5055 ms |
1016 KB |
subtask_01_06.txt |
AC |
4078 ms |
1016 KB |
subtask_01_07.txt |
AC |
4170 ms |
1016 KB |
subtask_01_08.txt |
AC |
4735 ms |
1016 KB |
subtask_01_09.txt |
AC |
4323 ms |
1016 KB |
subtask_01_10.txt |
AC |
4113 ms |
1016 KB |