Submission #1225132
Source Code Expand
#include <vector>
#include <cfloat>
#include <cstdio>
#include <cstring>
#include <ctime>
#include <cstdlib>
#include <cmath>
#include <string>
#include <iostream>
#include <cstdint>
#include <algorithm>
#include <cassert>
#include <random>
#include <queue>
#include <list>
#include <map>
#include <array>
#include <chrono>
using namespace std;
typedef long long ll;
#define N 50
#define beam_width 5
char S[N + 5][N + 5];
char ans[N + 5][N + 5];
char dummy[N + 5][N + 5];
int OK[N + 5][N + 5] = { 0 };
void fall();
int calc_score();
void beam_search();
int rank_check(int play);
void SA();
template<typename T>
using Board = array<array<T, N + 2>, N + 2>;
int dfs(int y, int x, Board<bool> &visited, const char ch);
struct data {
int score;
char state[N + 5][N + 5];
}node[beam_width], temp, dum[beam_width];
array<int, 4> dxs = { 0, 1, 0, -1 };
array<int, 4> dys = { 1, 0, -1, 0 };
double temperature(double start, double end, double r);
double probability(double e1, double e2, double t);
void gen_rand_next_field(const char c_field[N + 5][N + 5], char n_field[N + 5][N + 5]);
ll make_rand();
double gen_per_rand(const ll res = 1LL << 60) {
return 1.0 * (make_rand() % res) / (res - 1);
}
chrono::system_clock::time_point start;
int main() {
start = chrono::system_clock::now();
int i, j;
for (i = 0; i < N; i++) {
scanf("%s", &S[i]);
}
for (i = 0; i < N; i++) {
for (j = 0; j < N; j++) {
if (S[i][j] == '.') { OK[i][j] = 1; }
}
}
//beam_search();
SA();
return 0;
}
int dfs(int y, int x, Board<bool> &visited, const char ch)
{
int ans = 1;
visited[y][x] = true;
for (int i = 0; i < 4; i++)
{
const int ny = y + dys[i];
const int nx = x + dxs[i];
if (0 <= ny&&ny < N && 0 <= nx&&nx < N) {
if (!visited[ny][nx] && S[ny][nx] == ch)
{
ans += dfs(ny, nx, visited, ch);
}
}
}
return ans;
}
void fall() {
int i, j;
for (j = 0; j < N; j++) {
int tgt = N - 1;
for (i = N - 1; i >= 0; i--) {
if (S[i][j] == '-') {
tgt = i - 1;
}
else if (S[i][j] != '.') {
char c = S[i][j];
S[i][j] = '.';
S[tgt][j] = c;
tgt--;
}
}
}
}
int calc_score() {
Board<bool> visited;
for (auto &ary : visited)
{
fill(ary.begin(), ary.end(), false);
}
int score_x = 0;
int score_o = 0;
for (int y = 0; y < N; y++)
{
for (int x = 0; x < N; x++)
{
if (!visited[y][x])
{
if (S[y][x] == 'o')
{
score_o = max(score_o, dfs(y, x, visited, 'o'));
}
if (S[y][x] == 'x')
{
score_x = max(score_x, dfs(y, x, visited, 'x'));
}
}
}
}
return score_x + score_o;
}
void beam_search() {
int i, j, k, m;
for (i = 0; i < beam_width; i++) {
node[i].score = 0;
memcpy(node[i].state, S, sizeof(S));
}
int size = 1;
char c[3] = { '.','+','-' };
int rank, dumsize;
time_t stime = time(NULL);
while (1) {
for (i = N - 1; i >= 0; i--) {
for (j = N - 1; j >= 0; j--) {
dumsize = 0;
if (OK[i][j] == 1) {
for (k = 0; k < size; k++) {
for (m = 0; m < 3; m++) {
if (time(NULL) - stime > 5) {
int best = -(1 << 30);
int index;
int a;
for (a = 0; a < beam_width; a++) {
if (best < node[a].score) {
best = node[a].score;
index = a;
}
}
memcpy(ans, node[index].state, sizeof(node[index].state));
return;
}
temp = node[k];
temp.state[i][j] = c[m];
memcpy(S, temp.state, sizeof(temp.state));
fall();
temp.score = calc_score();
if (dumsize < beam_width) {
dum[dumsize] = temp;
dumsize++;
}
else if (dumsize == beam_width) {
rank = rank_check(beam_width);
if (temp.score > dum[rank].score) {
dum[rank] = temp;
}
}
}
}
}
else { continue; }
for (k = 0; k < dumsize; k++) {
node[k] = dum[k];
}
size = dumsize;
}
}
}
}
int rank_check(int play) {
int i;
int worst = (1 << 30);
int index;
for (i = 0; i<play; i++) {
if (worst>dum[i].score) {
worst = dum[i].score;
index = i;
}
}
return index;
}
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);
return res;
}
}
void gen_rand_next_field(const char c_field[N + 5][N + 5], char n_field[N + 5][N + 5]) {
const int col = make_rand() % N;
int i,j;
for (i = 0; i < N; i++) {
for (j = 0; j < N; j++) {
n_field[i][j] = c_field[i][j];
}
}
for (i = 0; i < N; i++) {
if (gen_per_rand() <= 0.5) {
if (OK[i][col] == 1) {
double p = gen_per_rand();
char c = '.';
if (p <= 0.8) { c = '.'; }
else if (p <= 0.9) {
c = '+';
}
else {
c = '-';
}
n_field[i][col] = c;
}
}
}
}
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));
}
/*
void SA() {
time_t stime = time(NULL);
random_device rd;
mt19937 mt(rd());
uniform_int_distribution<int> dice1(0, 2);
uniform_int_distribution<int> dice2(0, N - 1);
uniform_int_distribution<int> dice3(0, N - 1);
uniform_real_distribution<double> dice4(0, 1.0);
char c[3] = { '+','-','.' };
memcpy(ans,S,sizeof(S));//
memcpy(dummy, ans, sizeof(ans));
memcpy(S, ans, sizeof(ans));
fall();
int before = calc_score();
int after;
int c_score = before;
//printf("before=%d\n",before);
const int MAX_ITER = 1000000;
const double start_tmp = 10.0;
const double end_tmp = 1.0;
for (int iter = 0; iter < MAX_ITER; iter++) {
if (time(NULL) - stime > 9) {
printf("score=%d,it=%d\n",before,iter);
break;
}
char tmp[N + 5][N + 5];
memcpy(tmp,dummy,sizeof(dummy));
//gen_rand_next_field();
int cnt = 0;
while (1) {
int y = dice2(mt);
int x = dice3(mt);
if (OK[y][x] == 1) {
cnt++;
dummy[y][x] = c[dice1(mt)];
if (cnt >= 3) {
break;
}
}
}
memcpy(S, dummy, sizeof(dummy));
fall();
after = calc_score();
if (after > before) {
memcpy(ans, dummy, sizeof(dummy));
before = after;
}
double a = probability((double)c_score, (double)after, temperature(start_tmp, end_tmp, 1.0 * (double)iter / (double)MAX_ITER));
printf("%f\n",a);
if (dice4(mt) <= a) {
c_score = after;
}
else {
memcpy(dummy, tmp, sizeof(tmp));
}
}
}
*/
void SA() {
time_t stime = time(NULL);
char c[3] = { '+','-','.' };
memcpy(ans, S, sizeof(S));
memcpy(S, ans, sizeof(ans));
fall();
char c_field[N + 5][N + 5];
memcpy(c_field, ans, sizeof(ans));
int c_score = calc_score();
char b_field[N + 5][N + 5];
memcpy(b_field, c_field, sizeof(c_field));
int b_score = c_score;
const int MAX_ITER = 250000;
const double start_tmp = 1.0;
const double end_tmp = 0.1;
for (int iter = 0; iter < MAX_ITER; iter++) {
//if (iter % 1000 == 0) {
// cout << iter << " " << c_score << endl;
//}
// 時間になったので打ち切り
double diff = chrono::duration_cast<chrono::milliseconds>(chrono::system_clock::now() - start).count() / 1000.;
if (diff > 9.99) {
break;
}
char n_field[N + 5][N + 5];
gen_rand_next_field(c_field, n_field);
memcpy(S, n_field, sizeof(n_field));
fall();
int n_score = calc_score();
// 最高の値を更新
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(c_field, n_field, sizeof(n_field));
c_score = n_score;
}
}
//cout << "best_score : " << b_score << endl;
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
cout << b_field[i][j];
}
cout << endl;
}
}
Submission Info
Submission Time
2017-04-16 05:40:50+0900
Task
A - ○×ブロック
User
tekitouk
Language
C++14 (GCC 5.4.1)
Score
7180
Code Size
8221 Byte
Status
AC
Exec Time
9992 ms
Memory
256 KB
Compile Error
./Main.cpp: In function ‘int main()’:
./Main.cpp:68:20: warning: format ‘%s’ expects argument of type ‘char*’, but argument 2 has type ‘char (*)[55]’ [-Wformat=]
scanf("%s", &S[i]);
^
./Main.cpp:68:21: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
scanf("%s", &S[i]);
^
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
649 / 2500
766 / 2500
679 / 2500
667 / 2500
850 / 2500
711 / 2500
735 / 2500
770 / 2500
680 / 2500
673 / 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
AC
9992 ms
256 KB
subtask_01_02.txt
AC
9992 ms
256 KB
subtask_01_03.txt
AC
9992 ms
256 KB
subtask_01_04.txt
AC
9992 ms
256 KB
subtask_01_05.txt
AC
9992 ms
256 KB
subtask_01_06.txt
AC
9992 ms
256 KB
subtask_01_07.txt
AC
9992 ms
256 KB
subtask_01_08.txt
AC
9992 ms
256 KB
subtask_01_09.txt
AC
9992 ms
256 KB
subtask_01_10.txt
AC
9992 ms
256 KB