题解：AT_ahc050_a [AHC050A] Gamble on Ice

题意

让你构造一个序列

{P}

（放置岩石的顺序），使得按照序列依次放置岩石时，让机器人存活的步数最大化。并且在每一步中，机器人会随机选择一个方向滑行直到撞到岩石或边界，然后我们在序列

{P}

中的下一个位置放置岩石。如果机器人恰好位于该位置，则游戏结束；否则，我们获得

{1}

元奖金。

观察 & 思路

观察

机器人的移动是随机的，但是通过~玩那个小游戏~运行网页版可以发现，在机器人会长期停留在中心部分的格子，然后角落的格子访问的概率会很低。优先放置在概率低的格子使存活概率提升。

思路

计算每个空格在初始地图下的平稳分布概率（机器人长期位于该格子的概率）。平稳分布通过迭代求解马尔可夫链的转移矩阵得到。然后，按照平稳分布概率从小到大的顺序放置岩石（即先放置低概率格子）。

代码

CPP

#include <iostream>
#include <vector>
#include <map>
#include <algorithm>
#include <cmath>

using namespace std;

int main()
{
    int N,M;
    cin>>N>>M;
    vector<string> Grid(N);
    for(int I=0;I<N;I++)
    {
        cin>>Grid[I];
    }

    vector<pair<int,int>> FreeCells;
    for(int I=0;I<N;I++)
    {
        for(int J=0;J<N;J++)
        {
            if(Grid[I][J]=='.')
            {
                FreeCells.push_back({I,J});
            }
        }
    }

    int L=FreeCells.size();
    if(L==0)
    {
        return 0;
    }

    map<pair<int,int>,int> CellToIndex;
    for(int Idx=0;Idx<L;Idx++)
    {
        CellToIndex[FreeCells[Idx]]=Idx;
    }

    vector<vector<int>> NextState(L,vector<int>(4));
    vector<pair<int,int>> Dirs={{-1,0},{1,0},{0,-1},{0,1}};

    for(int Idx=0;Idx<L;Idx++)
    {
        int I=FreeCells[Idx].first;
        int J=FreeCells[Idx].second;
        for(int D=0;D<4;D++)
        {
            int Dx=Dirs[D].first;
            int Dy=Dirs[D].second;
            int Nx=I+Dx,Ny=J+Dy;
            int PrevX=I,PrevY=J;
            while(true)
            {
                if(Nx<0||Nx>=N||Ny<0||Ny>=N)
                {
                    break;
                }
                if(Grid[Nx][Ny]=='#')
                {
                    break;
                }
                PrevX=Nx;
                PrevY=Ny;
                Nx+=Dx;
                Ny+=Dy;
            }
            NextState[Idx][D]=CellToIndex[{PrevX,PrevY}];
        }
    }

    vector<double> Pi(L,1.0/L);
    const int MaxIter=200;

    for(int Iter=0;Iter<MaxIter;Iter++)
    {
        vector<double> PiNext(L,0.0);
        for(int U=0;U<L;U++)
        {
            for(int D=0;D<4;D++)
            {
                int V=NextState[U][D];
                PiNext[V]+=Pi[U]*0.25;
            }
        }
        Pi=PiNext;
    }

    vector<int> Indices(L);
    for(int I=0;I<L;I++)
    {
        Indices[I]=I;
    }

    sort(Indices.begin(),Indices.end(),[&](int A,int B)
    {
        if(fabs(Pi[A]-Pi[B])>1e-9)
        {
            return Pi[A]<Pi[B];
        }
        return FreeCells[A]<FreeCells[B];
    });

    for(int Idx:Indices)
    {
        cout<<FreeCells[Idx].first<<" "<<FreeCells[Idx].second<<endl;
    }

    return 0;
}

结

无，只是希望 RMJ 尽快变好。还有这

{0}

Byte 的数据是怎么做到的？安利一篇自己的博客点此跳转。

题解：AT_ahc050_a [AHC050A] Gamble on Ice

文章操作

题意

观察 & 思路

观察

思路

代码

结

相关推荐

评论

题解：AT_ahc050_a [AHC050A] Gamble on Ice