裏紙

ほぼ競プロ、たまに日記

ARC 019 C - 最後の森

問題

C: 最後の森 - AtCoder Regular Contest 019 | AtCoder

問題概要

R*Cの広さのグリッド上を村からスタートしほこらを通ってから城に向かいたいが,特定のマスには強敵がいて,そのマスに止まると戦闘が起こる.強敵との戦闘はK回以内に抑えたい(戦闘が終わったマスの強敵は二度と出現しなくなる).このとき,移動回数の最小値を求めよ.

  •  1 \le R \le 50
  •  1 \le C \le 50
  •  1 \le K \le 100

イデア

解説を見ながらまとめる.

倒した敵が復活しないということから,倒した敵の位置を保存しながら探索していくのはメモリ制約的に不可能になってくる.そこで,探索していく中で,明らかにムダな移動となるものを排除して最適性を保ちながら探索出来ると嬉しい.では,その最適性を保つというのがどういうことか考察してみる.

まず,上の考察からも倒した敵を情報として持つのは無理である.そこでこの情報を保存しなくてもいいように探索をできるようにしたい.そのために,中継地点というポイントを導入する.

村→ほこら→城という移動のルートを考えた時,まずほこらに向かっていくわけだが,そこで通ったある経路に対して,ほこらに着いた後に通る経路が一旦その道を外れてから合流するというのは効率が悪いので考える必要が無い.それは,その戻る地点をXとした時にほこらからXへ行くのに帰りに通ったほうが短いルートになるのなら行きもそこを通る方が移動回数的に得である(戦闘回数が変わらない,もしくは減るので).逆に戦闘回数を抑えたルートを通るのなら,Xにたどり着くときもその戦闘回数を抑えるルートを通らないと意味がないものとなってしまう.つまり村→X→ほこら→X→城というルートが見えてくる.このXが中継地点となる,

このXを固定すると,3つの移動経路を個別に考えて足し合わせることで最適な移動ルートを求めることができる.Xをスタートとして,dp[x][y][i]=Xから(x,y)に移動するのに合計の戦闘がi回以下で移動するのに必要な移動回数の最小値をBFSしながら更新していくことになる.

このDPを計算すると解が計算できる.a+b+c \le K (a,b,c, \ge 0)に対して,

  • Xに強敵がいない :  ans = min \{ dp_{村,a} + 2*dp_{ほこら,b} + dp_{城,c} \}
  • Xに強敵がいる :  ans = min \{ dp_{村,a} + 2*dp_{ほこら,b+1} + dp_{城,c+1} \} (Xの強敵を重複してカウントするのを除くため)

という形になる.すると1つのXに対してBFSによってdpテーブルがO(RCK)で計算できる.そして,答えを決めるためにa,b,cを探索しないといけないのでO(K^3)かかることになる.よって計算量はO(R^2 C^2 K + RCK^3)となる.残念ながら,後者の計算量が重くなる可能性があり,これでは間に合わない.

ここで,逆に考えてみる.つまり,

  • dp1[x][y][i]=村から(x,y)に移動するのに合計の戦闘がi回以下で移動するのに必要な移動回数の最小値
  • dp2[x][y][i]=ほこらから(x,y)に移動するのに合計の戦闘がi回以下で移動するのに必要な移動回数の最小値
  • dp3[x][y][i]=城から(x,y)に移動するのに合計の戦闘がi回以下で移動するのに必要な移動回数の最小値

というものを考える.これらはBFSによってO(RCK)で計算できることは,先ほどの考察からも分かることである.さて,これで先ほどと同じようにXに対して全探索することにすると,a+b+c \le K (a,b,c, \ge 0)に対して,

  • Xに強敵がいない :  ans = min \{ dp1_{X,a} + 2*dp2_{X,b} + dp3_{X,c} \}
  • Xに強敵がいる :  ans = min \{ dp1_{X,a} + 2*dp2_{X,b+1} + dp3_{X,c+1} \} (Xの強敵を重複してカウントするのを除くため)

これってさっきと計算量同じなのでは,と思ったがただa,b,cに対して全探索するともちろんそうなってしまう.そこで次のように2段階に分けることで計算量を分ける(!) これはdpのテーブルを分けたから実現できることである.具体的には,

  • v[x] = "x=a+b"であるときの dp1 + 2*dp2 の最小値
  • w[y] = "y=x+c"であるときの v[x] + dp3 の最小値

と段階に分けて計算していくことでここの計算量をO(K^2)におさえることが出来る.全体として計算量がO(RCK^2)となって,間に合う.

実装(C++)

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

typedef long long ll;
#define rep(i,n) for(int (i)=0;(i)<(int)(n);++(i))
#define each(itr,c) for(__typeof(c.begin()) itr=c.begin(); itr!=c.end(); ++itr)
#define all(x) (x).begin(),(x).end()
#define mp make_pair
#define pb push_back
#define fi first
#define se second

typedef pair<int,int> pi;
typedef pair<pi,int> P;
const int INF = 12345678;

int R,C,K;
int dp[3][50][50][102];
int dx[4]={1,-1,0,0}, dy[4]={0,0,1,-1};

bool in(pi z)
{
    return (0<=z.fi&&z.fi<R && 0<=z.se&&z.se<C);
}

int main()
{
    cin >>R >>C >>K;
    vector<string> s(R);
    rep(i,R) cin >>s[i];

    //村,ほこら,城 の位置
    pi p[3];
    rep(i,R)rep(j,C)
    {
        if(s[i][j]=='S') p[0]=pi(i,j);
        if(s[i][j]=='C') p[1]=pi(i,j);
        if(s[i][j]=='G') p[2]=pi(i,j);
    }

    //初期化
    fill(dp[0][0][0], dp[3][0][0], INF);
    //p[i]をスタート地点として
    rep(i,3)
    {
        dp[i][p[i].fi][p[i].se][0]=0;
        //(位置,戦闘回数)を保存してBFS
        queue<P> que;
        que.push(P(p[i],0));
        while(!que.empty())
        {
            P state = que.front();
            que.pop();

            //現在位置
            pi now = state.fi;
            //戦闘回数
            int num = state.se;
            rep(j,4)
            {
                pi nx(now.fi+dy[j], now.se+dx[j]);
                if(in(nx) && s[nx.fi][nx.se]!='T')
                {
                    int nxnum = num;
                    if(s[nx.fi][nx.se]=='E') ++nxnum;
                    if(nxnum>101) continue;

                    if(dp[i][nx.fi][nx.se][nxnum] > dp[i][now.fi][now.se][num]+1)
                    {
                        dp[i][nx.fi][nx.se][nxnum] = dp[i][now.fi][now.se][num]+1;
                        que.push(P(nx,nxnum));
                    }
                }
            }
        }
    }

    //最小値の伝播
    rep(i,3)rep(j,R)rep(k,C)
    {
        int minv=dp[i][j][k][0];
        for(int l=1; l<=K; ++l)
        {
            if(minv > dp[i][j][k][l]) minv=dp[i][j][k][l];
            dp[i][j][k][l]=minv;
        }
    }

    int ans = INF;

    //中継地点Xの位置を固定
    rep(i,R)rep(j,C)
    {
        //木のある位置を中継地点にするのは無理
        if(s[i][j]=='T') continue;

        bool enemy=false;
        if(s[i][j]=='E') enemy=true;

        int v[102];
        fill(v,v+102,INF);

        rep(x,K+1)rep(a,x+1)
        {
            int b=x-a;
            if(enemy) ++b;
            v[x] = min(v[x], dp[0][i][j][a]+2*dp[1][i][j][b]);
        }

        int w[102];
        fill(w,w+102,INF);
        rep(y,K+1)rep(x,y+1)
        {
            int c=y-x;
            if(enemy) ++c;
            w[y] = min(w[y], v[x]+dp[2][i][j][c]);
        }

        rep(y,K+1) ans = min(ans,w[y]);
    }

    if(ans>=INF) ans=-1;
    cout << ans << endl;
    return 0;
}