naoya_t@topcoder

Member SRM471 Medium(500): ThirteenHard (再考)

SRM, 過去問 | 12:43 |

（最初に書いたコードはこちら: https://topcoder-g-hatena-ne-jp.jag-icpc.org/n4_t/20100527/1274893027 ）

• (N-1)番目に到達すると分かっている（最短かは分からない）時刻があるなら、それ以降の時刻については検証無意味。
  • priority_queueを使ったほうがスマートかな。
• int[25][2^13]である駅までの最短時間が分かったとしても、その後でmod13死にするかもしれないのでmod13が違うやつは生かしておくべき。最短との比較枝切りをやめると最悪ケースでTLE。
  • やっぱりint[25][13][2^13]でないと駄目。
• それから

    ...
    bool boo = false;
    if (sm>0) {
      for(int k=0,p=1; k<13; k++,p<<=1){
        if (msk & p) {
          if (((sm + 13) - k) % 13 == 0) { boo=true; break; }
        }
      }
    }
    if (boo) continue;
    ...

ここは

    if (msk & (1 << (sm % 13))) continue;

と等価ではないか！

勿論、C/C++の演算子の優先順位に従えば括弧は省略できて

    if (msk & 1 << sm % 13) continue;

と書けるが直感的にこれが(msk&1)<<(sm%13)などに見えてしまって怖くてたまらない。

• てな感じで書き直したのがこれ:

#define sz(a)  int((a).size())
#define pb  push_back
#define all(c)  (c).begin(),(c).end()
#define tr(c,i)  for(typeof((c).begin()) i=(c).begin(); i!=(c).end(); i++)
#define rep(var,n)  for(int var=0;var<(n);var++)
#define found(s,e)  ((s).find(e)!=(s).end())

typedef pair<int,int> ii;
typedef pair<int,ii> iii;
#define cons(x,y) make_pair((x),(y))
#define car(x) ((x).first)
#define cdr(x) ((x).second)
#define cadr(x) (x).second.first
#define cddr(x) (x).second.second

#define INF 987654321 // 13で割り切れない

class ThirteenHard {
  int conv(char c){
    int d = INF;
    if ('A'<=c && c<='Z') d = 1+(c-'A');
    else if ('a'<=c && c<='z') d = 27+(c-'a');
    return d%13 ? d : INF;
  }

 public:
  int calcTime(vector <string> city) {
    int n=sz(city);
    vector<vector<int> > ds(n,vector<int>(n));
    rep(i,n) rep(j,n) ds[i][j] = conv(city[i][j]);

    vector<vector<vector<int> > > e(n,vector<vector<int> >(13,vector<int>(8192,INF)));

    int goal = n-1;

    priority_queue<iii> q;
    q.push( cons(0,cons(0,0)) );
    while(!q.empty()) {
      iii t=q.top(); q.pop();
      int sm=-car(t), wh=cadr(t), msk=cddr(t);
      int msk2 = msk; if (sm > 0) msk2 |= 1 << sm % 13;

      if (sm >= e[wh][sm%13][msk2]) continue;

      if (wh == goal) return sm;
      e[wh][sm%13][msk2] = sm;
      for(int j=0,m=1; j<n; j++,m<<=1) {
        int d_ = ds[wh][j];
        if (d_ != INF) {
          int sm2 = sm + d_;
          if (sm2 % 13 == 0) continue;
          if (msk2 & 1 << sm2 % 13) continue;
          q.push( cons(-sm2,cons(j, msk2)) );
        }
      }
    }
    return -1;
  }
};

• passed system test.

追記

• スタート地点からのラップタイムではなく、スタート以降現在までの全地点から現在地点までの所要時間（のmod13）を持てばint[25][2^13]でいいのか。
  • 余り0なら持つ必要がないのでint[25][2^12]で良いとか（by cafelier先生）