Codeforces Round 878 (Div. 3) - F. Railguns (2200)

F. Railguns

문제에 뭔가 이상이 있었던 모양인데, 까다로운 DP이다.

에디토리얼이 쓸모가없다. 그냥 내가 푼 방법을 설명한다.

$dp[y][x][t]$ 를 $y,x$ 자리에 $t$ 번째 시간에 도달하는 최단 시간이라고 하자.

여기서 $t$는 실제 시간이 아닌 나오는 시간들을 좌표압축한 인덱스이다.

즉, $dp[y][x][t]$는 $[T_t \sim T_{t+1})$ 시간에 $(y,x)$ 에 있기 위한 최단 시간이다.

$T_t + 1 = T_{t+1}$ 인 경우만 좀 잘 고려해주고 미리 $die[y][x][t]$ 로 $t$ 시점에 $y,x$에 있으면 레일건을 맞고 뒈지는지를 전처리해두면 $O(nmt^2)$ 정도로 구할 수 있다. 실제론 거의 $O(nmt)$ 에 돈다.

const int inf = 2e9;
const int dy[] = {0, 1}, dx[] = {1, 0};
void solve() {
   int Y, X, R;
   cin >> Y >> X >> R;
   Y++, X++;
 
   vi tval;
   vector<array<int, 3>> shot;
   for (int i = 0; i < R; i++) {
      int t, d, coord;
      cin >> t >> d >> coord;
      // d = 1 horizontal 0 ~ Y
      // d = 2 vertical 0 ~ X
      tval.pb(t);
      shot.pb({t, d, coord});
   }
   tval.pb(0);
   uniq(tval);
 
   int T = sz(tval);
   tval.pb(inf);
   // y, x에 t 시점에 레이저가 쏴지는가?
   vector<vvi> die(Y, vvi(X, vi(T)));
   for (auto &[t, d, coord]: shot) {
      t = lbi(tval, t);
      if (d == 1)
         for (int x = 0; x < X; x++) die[coord][x][t] = 1;
      else
         for (int y = 0; y < Y; y++) die[y][coord][t] = 1;
   }
 
 
 
   // y, x에서 tval[t] 이상의 시점에 제일 빨리 도달할 수 있는 최단거리
   vector<vvi> dp(Y + 2, vvi(X + 2, vi(T + 2, inf)));
   dp[0][0][0] = 0;
   debug(tval);
   for (int y = 0; y < Y; y++) {
      for (int x = 0; x < X; x++) {
         for (int t = 0; t < T; t++) {
            if (dp[y][x][t] == inf) continue;
 
            for (int d = 0; d < 2; d++) {
               int ny = y + dy[d], nx = x + dx[d];
               if (ny >= 0 && ny < Y && nx >= 0 && nx < X) {
 
                  if (dp[y][x][t] + 1 != tval[t + 1]) {
                     mina(dp[ny][nx][t], dp[y][x][t] + 1);
                  }
 
                  for (int nt = t + 1; nt < T; nt++) {
 
                     if (!die[ny][nx][nt]) {
                        mina(dp[ny][nx][nt], tval[nt]);
                     } else if (tval[nt] + 1 != tval[nt + 1] && !die[y][x][nt]) {
                        mina(dp[ny][nx][nt], tval[nt] + 1);
                     }
 
                     if (die[y][x][nt]) break;
                  }
               }
            }
         }
      }
   }
   int ans = inf;
   for (int t = 0; t < T; t++) {
      if (dp[Y - 1][X - 1][t] != inf) {
         mina(ans, dp[Y - 1][X - 1][t]);
      }
   }
   if (ans == inf) cout << -1 << endl;
   else cout << ans << endl;
}