提出 #73454991

---

ソースコード 拡げる

#include <bits/stdc++.h>
using namespace std;

static const int DX[4] = {1,-1,0,0};
static const int DY[4] = {0,0,1,-1};

int N,M,T,U;
vector<vector<int>> V;
vector<pair<int,int>> start_pos;

struct State {
    vector<pair<int,int>> pos;
    vector<vector<int>> owner;
    vector<vector<int>> level;
};

bool in_bounds(int x,int y){
    return x>=0 && x<N && y>=0 && y<N;
}

// BFS で到達可能領土取得
vector<pair<int,int>> get_reachable(int pid, const State& st){
    vector<pair<int,int>> res;
    queue<pair<int,int>> q;
    vector<vector<int>> vis(N, vector<int>(N,0));

    auto [sx,sy]=st.pos[pid];
    q.push({sx,sy});
    vis[sx][sy]=1;

    while(!q.empty()){
        auto [x,y]=q.front(); q.pop();
        if(st.owner[x][y]!=pid) continue;
        res.push_back({x,y});
        for(int d=0;d<4;d++){
            int nx=x+DX[d], ny=y+DY[d];
            if(in_bounds(nx,ny)&&!vis[nx][ny]){
                vis[nx][ny]=1;
                q.push({nx,ny});
            }
        }
    }
    return res;
}

// 合法手集合
vector<pair<int,int>> get_candidates(int pid,const State& st){
    auto reach=get_reachable(pid,st);
    set<pair<int,int>> cand;
    for(auto [x,y]:reach){
        cand.insert({x,y});
        for(int d=0;d<4;d++){
            int nx=x+DX[d], ny=y+DY[d];
            if(in_bounds(nx,ny))
                cand.insert({nx,ny});
        }
    }
    // 他プレイヤー駒除外
    for(int i=0;i<M;i++){
        if(i==pid) continue;
        cand.erase(st.pos[i]);
    }
    return vector<pair<int,int>>(cand.begin(), cand.end());
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin>>N>>M>>T>>U;
    V.assign(N,vector<int>(N));
    for(int i=0;i<N;i++)
        for(int j=0;j<N;j++)
            cin>>V[i][j];

    start_pos.resize(M);
    for(int i=0;i<M;i++)
        cin>>start_pos[i].first>>start_pos[i].second;

    State st;
    st.pos=start_pos;
    st.owner.assign(N,vector<int>(N,-1));
    st.level.assign(N,vector<int>(N,0));
    for(int i=0;i<M;i++){
        auto [x,y]=start_pos[i];
        st.owner[x][y]=i;
        st.level[x][y]=1;
    }

    for(int turn=0;turn<T;turn++){

        // 自分の候補
        auto cand0=get_candidates(0,st);

        // AIごとの確率分布
        vector<vector<double>> P(M, vector<double>(N*N,0.0));

        for(int pid=1;pid<M;pid++){
            auto cand=get_candidates(pid,st);
            if(cand.empty()) continue;

            int K=cand.size();
            vector<double> score(K);

            for(int i=0;i<K;i++){
                auto [x,y]=cand[i];
                int owner=st.owner[x][y];
                int lv=st.level[x][y];
                double val=V[x][y];
                if(owner==-1) score[i]=val;
                else if(owner==pid){
                    if(lv<U) score[i]=val;
                    else score[i]=0;
                }
                else{
                    if(lv==1) score[i]=val;
                    else score[i]=val*0.5;
                }
            }

            double mx=*max_element(score.begin(),score.end());
            int cnt=0;
            for(double s:score)
                if(abs(s-mx)<1e-9) cnt++;

            double eps=0.3; // 固定近似
            for(int i=0;i<K;i++){
                double prob=eps*(1.0/K);
                if(abs(score[i]-mx)<1e-9)
                    prob+=(1.0-eps)*(1.0/cnt);
                int idx=cand[i].first*N + cand[i].second;
                P[pid][idx]=prob;
            }
        }

        // 手評価
        double best_score=-1e18;
        pair<int,int> best_move=cand0[0];

        for(auto [x,y]:cand0){

            double survive=1.0;
            int idx=x*N+y;
            for(int pid=1;pid<M;pid++)
                survive*= (1.0 - P[pid][idx]);

            int owner=st.owner[x][y];
            int lv=st.level[x][y];

            double gain=0;
            if(owner==-1) gain=V[x][y];
            else if(owner==0){
                if(lv<U) gain=V[x][y];
            }
            else{
                if(lv==1) gain=2*V[x][y];
                else gain=-V[x][y];
            }

            if(turn>60) gain*=1.5;

            double eval=survive*gain;

            if(eval>best_score){
                best_score=eval;
                best_move={x,y};
            }
        }

        cout<<best_move.first<<" "<<best_move.second<<endl;
        cout.flush();

        // 盤面更新読み込み
        vector<pair<int,int>> tx(M), ex(M);
        for(int i=0;i<M;i++)
            cin>>tx[i].first>>tx[i].second;
        for(int i=0;i<M;i++)
            cin>>ex[i].first>>ex[i].second;
        for(int i=0;i<N;i++)
            for(int j=0;j<N;j++)
                cin>>st.owner[i][j];
        for(int i=0;i<N;i++)
            for(int j=0;j<N;j++)
                cin>>st.level[i][j];

        st.pos=ex;
    }
}

提出情報

ジャッジ結果