Div1 500 ThirteenHard

SRM

問題

駅駅間の所要時間が2次元配列で与えられる．(A-Zは1〜26，a-zは27〜52，#は通行不可)
目的地に達するまでの各部分区間において所要時間が13の倍数になってはいけない．(※)
0番の駅からN-1番の駅まで達するのに要する最短時間を求めよ．

(※)4駅で移動した時，各駅間の所要時間が順に T0, T1, T2 だとするとき，T0, T1, T2, T0+T1, T1+T2, T0+T1+T2 のいずれも 13 の倍数になってはいけない．T0+T2は部分区間ではないのでなってもOK．

考え方

[N][213]の空間でダイクストラを行うのがよい．TwitterでDPとか言ったけどDPじゃないね．
dijk[i][j] については i 駅に達する時間を入れる．j は分かりにくいが「i 駅に達するまでの部分時間を13で割った余りのフラグ集」．i 駅に着くまでの各駅間の時間を順に T[0], T[1], … T[K] とするとき，

int a = 0;
for( int t = 0, k = K ; k >= 0 ; --k ) {
  t = (t + T[k]) % 13;
  a |= (1 << t);
}

で表される数 a．
i 駅より前で終わる区間について気にしないのは，

  1. その中に 13 の倍数があったら探索していないから．
  2. i 駅からの新しい移動により 13 で割った余りが変動しないから．

の2つの理由による．

あとは時間が短いものから順序付きキューに投げてダイクストラを行えばOK．

コード

#include <iostream>
#include <set>
#include <string>
#include <vector>
using namespace std;

struct Lap
{
  int time, city, flag;
  Lap(int a, int b, int c) : time(a), city(b), flag(c) {}
};
bool operator<(const Lap& a, const Lap& b)
{
  if( a.time == b.time ) {
    if( a.city == b.city ) return a.flag < b.flag;
    return a.city < b.city;
  }
  return a.time < b.time;
}

class ThirteenHard
{
  int distance(char c)
  {
    if( 'A' <= c && c <= 'Z' ) return c - 'A' + 1;
    return c - 'a' + 27;
  }
public:
  int calcTime(vector <string> city)
  {
    vector< vector<int> > shortest(25, vector<int>(99999, 1<<13));
    set<Lap> q;
    shortest[0][0] = 0;
    q.insert(Lap(0, 0, 0));
    while( !q.empty() ) {
      Lap l = *q.begin();
      q.erase(q.begin());
      if( l.city == city.size() - 1 ) return l.time;
      string& dist = city[l.city];
      for( int i = 0 ; i < city.size() ; ++i ) {
        if( dist[i] == '#' ) continue;
        int d = distance(dist[i]);
        int tt = l.time + d;
        int ff = (l.flag | 1) << (d % 13);
        ff = (ff | (ff >> 13)) & 0x1fff;
        if( ff & 1 ) continue;
        if( shortest[i][ff] > tt ) {
          shortest[i][ff] = tt;
          q.insert(Lap(tt, i, ff));
        }
      }
    }
    return -1;
  }
};