Submission #1755750

---

Source Code Expand

#include <iostream>
#include <cstdio>
#include <random>
#include <queue>
#include <string>
using namespace std;

#define rep(i,a,n) for(int i=a; i<n; i++)
template<typename T> void chmax(T &a, T b) { a = max(a, b); }
typedef long long int ll;
typedef pair<int, int> pii;

const int N = 50;
vector<string> board;
vector<pii> blank_pos;

int dx[] = {1, -1, 0, 0};
int dy[] = {0, 0, 1, -1};

struct Rand {
public:
    Rand() = default;
    Rand(std::mt19937::result_type seed) : eng(seed) {}
    int NextInt(int lb, int ub) {
        return std::uniform_int_distribution<int>{lb, ub}(eng);
    }
    ll NextLong(ll lb, ll ub) {
        return std::uniform_int_distribution<ll>{lb, ub}(eng);
    }
    double NextDouble(double lb, double ub) {
        return std::uniform_real_distribution<double>{lb, ub}(eng);
    }
private:
    std::mt19937 eng{std::random_device{}()};
};

struct Elem {
    int idx, score;
    vector<int> change_array;
    Elem(int a, int b, vector<int> c) : idx(a), score(b), change_array(c) {}

    // 一番評価の低いものが先頭に来るようにしたいので、
    // score が小さいものを優先するように書く
    bool operator<(const Elem &x) const {
        return score > x.score;
    }
};

int bfs(vector<string> &cur) {
    int ret_o = 0, ret_x = 0;
    bool used[N+10][N+10] = {};

    queue<pii> que;
    rep(i,0,N) rep(j,0,N) {
        if(used[i][j]) continue;
        used[i][j] = true;
        int temp_o = 0, temp_x = 0;
        if(cur[i][j] == 'o') temp_o++;
        if(cur[i][j] == 'x') temp_x++;
        que.push(make_pair(i, j));
        while(!que.empty()) {
            pii t = que.front(); que.pop();
            int x = t.first, y = t.second;

            // 今見ているマスと同じ種類のマスかつ未到達なら処理する
            rep(k,0,4) {
                int nx = x + dx[k];
                int ny = y + dy[k];
                if(nx < 0 || nx >= N || ny < 0 || ny >= N) continue;
                if(cur[nx][ny] != cur[x][y]) continue;
                if(used[nx][ny]) continue;
                used[nx][ny] = true;
                if(cur[nx][ny] == 'o') temp_o++;
                if(cur[nx][ny] == 'x') temp_x++;
                que.push(make_pair(nx, ny));
            }
        }
        chmax(ret_o, temp_o);
        chmax(ret_x, temp_x);
    }
    // fprintf(stderr, "ret_o = %d, ret_x = %d\n", ret_o, ret_x);
    return ret_o + ret_x;
}

void blockfall(vector<string> &cur) {
    for(int i=N-1; i>=0; i--) rep(j,0,N) {
        int x = i, y = j;

        // 自由落下しない
        if(cur[x][y] == '-') continue;

        while(1) {
            int nx = x + 1;

            // 一番下まで行った or 移動先にブロックが存在 -> 抜けよう
            if(nx >= N || cur[nx][y] != '.') break;
            swap(cur[nx][y], cur[x][y]);
            x++;
        }
    }
}

int evaluate(vector<int> &change_info) {
    vector<string> cur = board;
    int M = blank_pos.size();

    // change blocks
    rep(i,0,M) {
        int x = blank_pos[i].first, y = blank_pos[i].second;
        if(change_info[i] == 1) {
            // '.' -> '+'
            cur[x][y] = '+';
        }
        if(change_info[i] == 2) {
            // '.' -> '-'
            cur[x][y] = '-';
        }
    }

    blockfall(cur);
    return bfs(cur);
}

void print_board(vector<int> &chg) {
    int M = blank_pos.size();
    vector<string> ans = board;
    rep(i,0,M) {
        int x = blank_pos[i].first, y = blank_pos[i].second;
        if(chg[i] == 1) ans[x][y] = '+';
        if(chg[i] == 2) ans[x][y] = '-';
    }

    rep(i,0,N) {
        rep(j,0,N) printf("%c", ans[i][j]);
        printf("\n");
    }
    blockfall(ans);
    bfs(ans);
}

void solve() {
    // score を評価値とする。これが大きいほどよい
    int M = blank_pos.size();
    vector<int> chg(M, 0);
    int init_score = evaluate(chg);
    fprintf(stderr, "init_score = %d\n", init_score);

    int K = 30; // ビーム幅
    queue<Elem> que;
    que.push(Elem{0, init_score, chg});

    int max_score = 0;
    vector<int> max_chg;
    while(!que.empty()) {
        priority_queue<Elem> topK;
        while(!que.empty()) {
            Elem t = que.front(); que.pop();

            if(max_score < t.score) {
                max_score = t.score;
                max_chg = t.change_array;
            }

            int cur_idx = t.idx;
            if(cur_idx == M) continue;
            rep(k,0,3) {
                t.change_array[cur_idx] = k;
                int new_score = evaluate(t.change_array);
                topK.push(Elem{cur_idx + 1, new_score, t.change_array});

                // topK のサイズは常に K 以下
                if((int)topK.size() == K+1) topK.pop();
            }
            // fprintf(stderr, "cur_idx = %d, size = %d\n", cur_idx, topK.size());
        }
        while(!topK.empty()) {
            que.push(topK.top());
            topK.pop();
        }
    }

    // 答えを出力
    print_board(max_chg);
}

int main() {
    board.resize(N);
    rep(i,0,N) cin >> board[i];
    rep(i,0,N) rep(j,0,N) {
        if(board[i][j] == '.') blank_pos.push_back(make_pair(i, j));
    }
    solve();
    return 0;
}

Submission Info

Judge Result