Submission #1174818
Source Code Expand
#include <bits/stdc++.h>
#define DEBUG
using namespace std;
using pii = pair<int,int>;
using ll = long long;
const int N = 50; // N * N のfieldに対して計算
const double TIME_LIMIT = 9.5; // 実行制限時間
struct TimeWatch{
clock_t start_,end_;
void start(){start_=clock();}
double stop(){return (double)(clock()-start_)/CLOCKS_PER_SEC;}
} tw;
ll make_rand(){
static ll x=123456789;
static ll y=362436069;
static ll z=521288629;
static ll w=88675123;
ll t;
t=x^(x<<11);
x=y;y=z;z=w;
return w=(w^(w>>19))^(t^(t>>8));
}
bool is_time_limit(){
return (tw.stop() >= TIME_LIMIT);
}
const int dy[] = {-1, 0, 0, 1};
const int dx[] = {0, -1, 1, 0};
template<int N>
class UnionFindTree{
private:
// indexの数の親ノード(ある集合の親を見つけたいときはここを直接参照せず、findを使う)
int par[N];
// indexを根とする木のランク
int rank[N];
// 集合のサイズ
int cnts[N];
// 木の最大値
int treeSize;
public:
UnionFindTree(){
for(int i = 0; i < N; i++){
par[i] = i;
rank[i] = 0;
cnts[i] = 1;
}
}
// 与えられた数が格納されている木のルートを探索
int find(int x){
if(par[x] == x)return x;
else return par[x] = find(par[x]);
}
// 和集合をとる。ただしここでは各集合の親の付け替えは起こらない
void unite(int x,int y){
x = find(x);
y = find(y);
if(x == y)return;
if(rank[x] < rank[y]){
par[x] = y;
cnts[y]+=cnts[x];
}
else{
par[y] = x;
cnts[x]+=cnts[y];
if(rank[y] == rank[x])rank[x]++;
}
}
// xの属する集合のサイズ
int getCnt(int x){
return cnts[find(x)];
}
bool same(int x,int y){
return find(x) == find(y);
}
};
void drop(char field[N+1][N+1]){
// .である場所は落とす
for(int j = 0; j < N; j++){
int tgt = N - 1;
for(int i = N - 1; i >= 0; i--){
// もし.以外なら、.以外のマスまで落下
if(field[i][j] == '-'){
tgt = i - 1;
}
else if(field[i][j] != '.'){
char c = field[i][j]; // target
field[i][j] = '.';
field[tgt][j] = c;
tgt--;
}
}
}
}
// oとxの最大連結数の和
// fieldをdropしたあと、スコアを計算して出力する
int score(const char c_field[N+1][N+1], bool out = false){
char field[N+1][N+1];
memcpy(field, c_field, sizeof(field));
drop(field);
UnionFindTree<N*N> uft;
for(int y = 0; y < N; y++){
for(int x = 0; x < N; x++){
for(int k = 0; k < 4; k++){
int ny = y + dy[k];
int nx = x + dx[k];
if(ny >= 0 && nx >= 0 && ny < N && nx < N){
// 同じ要素は連結する
if(field[ny][nx] == field[y][x]){
int idx1 = y * N + x;
int idx2 = ny * N + nx;
uft.unite(idx1, idx2);
}
}
}
}
}
int max_o = 0;
int max_x = 0;
for(int y = 0; y < N; y++){
for(int x = 0; x < N; x++){
if(field[y][x] == 'o') max_o = max(max_o, uft.getCnt(y * N + x));
if(field[y][x] == 'x') max_x = max(max_x, uft.getCnt(y * N + x));
}
}
if(out){
for(int y = 0; y < N; y++){
for(int x = 0; x < N; x++){
const int cnt = uft.getCnt(y*N + x);
if(field[y][x] == 'o' && cnt == max_o){
cout << "@";
}
else if(field[y][x] == 'x' && cnt == max_x){
cout << "#";
}
else{
cout << field[y][x];
}
}
cout << endl;
}
}
return max_o + max_x;
}
double temperature(double start, double end, double r){
return start + (end - start) * r;
}
double probability(double e1, double e2, double t){
if(e1 <= e2){
return 1;
}
else{
double res = exp((-e1+e2)/t);
// cout << e1 << " " << e2 << " " << t << endl;
// cout << "drop: "<<res << endl;
return res;
}
}
// [0,1]の範囲で乱数を生成
double gen_per_rand(const ll res = 1LL << 60){
return 1.0 * (make_rand() % res) / (res - 1);
}
// n_fieldに次の状態をランダムで生成
void gen_rand_next_field(const char c_field[N+1][N+1], char n_field[N+1][N+1]){
// 一列ずつ変化させてくと良いらしい
// +と.と-との割合が大切らしい
// .を7割, +を2割, -を1割ぐらいで生成する?
const int col = make_rand() % N;
for(int i = 0; i < N + 1; i++)
for(int j = 0; j < N + 1; j++)
n_field[i][j] = c_field[i][j];
const double dot_per = 0.7;
const double plus_per = 0.1;
for(int i = 0; i < N; i++){
if(gen_per_rand() <= 0.5){
if(n_field[i][col] == '.' || n_field[i][col] == '+' || n_field[i][col] == '-'){
double p = gen_per_rand();
char &c = n_field[i][col];
if(p <= dot_per) c = '.';
else if(p <= dot_per + plus_per) c = '+';
else c = '-';
}
}
}
}
void solve(const char start_field[N+1][N+1]){
// 焼きなましの試行回数
const int MAX_ITER = 100000;
const double start_tmp = 10;
const double end_tmp = 1;
#ifdef DEBUG
int start_score = score(start_field);
cout << "start_score : " << start_score << endl;
score(start_field, true);
#endif
// 現在のfieldと、そのスコア
char c_field[N+1][N+1];
memcpy(c_field, start_field, sizeof(c_field));
int c_score = score(c_field);
// bestスコアのfieldと、そのスコア
char b_field[N+1][N+1];
memcpy(b_field, c_field, sizeof(c_field));
int b_score = c_score;
// 焼きなまし開始
for(int iter = 0; iter < MAX_ITER; iter++){
// 時間になったので打ち切り
if(is_time_limit()) break;
char n_field[N+1][N+1];
gen_rand_next_field(c_field, n_field);
int n_score = score(n_field);
// 最高の値を更新
if(n_score > b_score){
memcpy(b_field, n_field, sizeof(b_field));
b_score = n_score;
}
// 状態遷移するか判定
if(gen_per_rand() <= probability(c_score, n_score, temperature(start_tmp, end_tmp, 1.0 * iter / MAX_ITER))){
memcpy(n_field, c_field, sizeof(n_field));
c_score = n_score;
// #ifdef DEBUG
// cout << c_score << endl;
// #endif
}
}
#ifdef DEBUG
cout << "best_score : " << b_score << endl;
score(b_field, true);
#endif
#ifndef DEBUG
// printして終了
for(int i = 0; i < N; i++){
for(int j = 0; j < N; j++){
cout << b_field[i][j];
}
cout << endl;
}
#endif
}
void greedy(const char src[N+1][N+1], char dst[N+1][N+1]){
// srcの初期に値をコピーしておき、そこからgreedyに改善する
for(int i = 0; i < N; i++){
for(int j = 0; j < N; j++){
dst[i][j] = src[i][j];
}
}
int dst_score = score(dst);
// 下から順番に、改善できるところをすべてためす
bool update = true;
while(update){
update = false;
for(int i = N - 1; i >= 0; i--){
for(int j = 0; j < N; j++){
const char nxts[3] = {'.', '+', '-'};
int tgt = -1;
for(int k = 0; k < 3; k++){
if(dst[i][j] == nxts[k]){
tgt = k;
break;
}
}
if(tgt == -1) continue;
for(int k = 0; k < 3; k++){
if(k == tgt) continue;
char backup = dst[i][j];
// 変化させて、スコアを計算する
dst[i][j] = nxts[k];
int nxt_score = score(dst);
if(nxt_score > dst_score){
dst_score = nxt_score;
update = true;
break;
}
else{
// 元に戻す
dst[i][j] = backup;
}
}
if(update) break;
}
if(update) break;
}
}
return;
}
int main(){
tw.start(); // 時間計測開始
char field[N+1][N+1];
for(int i = 0; i < N; i++)
for(int j = 0; j < N; j++)
cin >> field[i][j];
// fieldをsolveにわたす前に、greedy等である程度値の良い初期解を生成したほうが良いかも
// 制限時間を考えつつ、やれる範囲で
char g_field[N+1][N+1];
greedy(field, g_field);
#ifdef DEBUG
cout << "greedy score : ";
cout << score(g_field) << endl;
#endif
solve(g_field);
return 0;
}
Submission Info
Submission Time |
|
Task |
A - ○×ブロック |
User |
ishikado |
Language |
C++14 (GCC 5.4.1) |
Score |
0 |
Code Size |
9726 Byte |
Status |
WA |
Exec Time |
9513 ms |
Memory |
640 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 |
0 / 2500 |
0 / 2500 |
0 / 2500 |
0 / 2500 |
0 / 2500 |
0 / 2500 |
0 / 2500 |
0 / 2500 |
0 / 2500 |
0 / 2500 |
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 |
WA |
9513 ms |
640 KB |
subtask_01_02.txt |
WA |
9502 ms |
256 KB |
subtask_01_03.txt |
WA |
9502 ms |
256 KB |
subtask_01_04.txt |
WA |
9513 ms |
512 KB |
subtask_01_05.txt |
WA |
9502 ms |
256 KB |
subtask_01_06.txt |
WA |
9502 ms |
256 KB |
subtask_01_07.txt |
WA |
9502 ms |
384 KB |
subtask_01_08.txt |
WA |
9502 ms |
256 KB |
subtask_01_09.txt |
WA |
9502 ms |
256 KB |
subtask_01_10.txt |
WA |
9502 ms |
256 KB |