Submission #1174832


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.8;
    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 = 50000;
    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 5957
Code Size 9727 Byte
Status AC
Exec Time 6502 ms
Memory 896 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 558 / 2500 674 / 2500 595 / 2500 589 / 2500 629 / 2500 523 / 2500 636 / 2500 579 / 2500 584 / 2500 590 / 2500
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 5682 ms 896 KB
subtask_01_02.txt AC 6401 ms 256 KB
subtask_01_03.txt AC 6220 ms 256 KB
subtask_01_04.txt AC 6300 ms 256 KB
subtask_01_05.txt AC 5495 ms 256 KB
subtask_01_06.txt AC 6070 ms 256 KB
subtask_01_07.txt AC 5779 ms 256 KB
subtask_01_08.txt AC 6396 ms 256 KB
subtask_01_09.txt AC 6502 ms 256 KB
subtask_01_10.txt AC 5854 ms 384 KB