2011 TCO Algorithm Qualification Round 2 medium

問題概要

マスが50個のすごろくみたいなのをする。
スタートゴールは普通のマス。
その他のマスにK, もしくはCと書かれている場合がある。
それ意外は普通のマス
また、K, C の二つの整数が与えられる。
すごろくをはじめてから経った時間をTとする。
T　％　K　＝＝　０　のとき、Kのマスには侵入及び滞在不可能であり、
T　％　C　！＝　０　のとき、Cのマスには侵入及び滞在不可能である。

解法

dp
状態が、今居る場所 × 今の時間のKによるmod x 今の時間のCによりmod
最初、たどり着ける手数を最大K＊Cと見積もって死亡

以下のソースでは、最大手数を200000と見積もって解いている。

ソース

include<string>
using namespace std;
#define REP(i,b,n) for(int i=b;i<(int)n;i++)
#define rep(i,n)   REP(i,0,n)
bool dp[200000][50];
class KindAndCruel {
public:
  int crossTheField(string field, int K, int C) {
    int n = field.length();
    rep(i, 200000)rep(j, 50)dp[i][j] = false;
    dp[0][0] = true;
    rep(i, 200000){
      rep(j, n){
        if(!dp[i][j])continue;
        if(field[j] == 'K' && i % K == 0)dp[i][j] = false;
        if(field[j] == 'C' && i % C != 0)dp[i][j] = false;
        if(!dp[i][j])continue;
        if(i+1 == 200000)continue;
        dp[i+1][max(0, j-1)] = dp[i+1][min(n-1, j+1)] = dp[i+1][j] = true;
      }
    }
    rep(i, 200000){
      if(dp[i][n-1])return i;
    }
    return -1;
  }
};