naoya_t@topcoder

SRM468 Medium: RoadOrFlightHard

過去問 | 23:50 |

DPでコード書いてみたら250より簡単で泣けた。DPって分かっただけで終了なゲームなのになぜ…

• 気をつけないとMLE食らいます。
  • 全部持っておくことない
  • long long [2][飛行機に乗った回数<=40][今の都市まで乗ってきたか否か]でいいじゃん...sizeof(long long)x2x41x2=1312(bytes)

typedef long long ll;
#define rep(var,n)  for(int var=0;var<(n);var++)

class RoadOrFlightHard {
 public:
  ll minTime(int N,
             int roadFirst, int roadProd, int roadAdd, int roadMod,
             int flightFirst, int flightProd, int flightAdd, int flightMod,
             int K) {
    vector<ll> roadTime(N), flightTime(N);
    roadTime[0]   =   roadFirst % roadMod;
    flightTime[0] = flightFirst % flightMod;
    for (int i=1; i<=N-1; i++) {
      roadTime[i]   = (roadTime[i-1]*roadProd + roadAdd) % roadMod;
      flightTime[i] = (flightTime[i-1]*flightProd + flightAdd) % flightMod;
    }

    ll m[2][K+1][2];
    rep(r,2) rep(k,K+1) rep(b,2) m[r][k][b] = LONG_LONG_MAX;

    m[0][0][0] = 0;

    for(int i=0; i<N; i++) {
      int r0 = i%2, r1 = (i+1)%2;
      rep(k,K+1) rep(b,2) m[r1][k][b] = LONG_LONG_MAX;
      rep(k,K+1) rep(b,2) {
        ll t = m[r0][k][b];
        if (t == LONG_LONG_MAX) continue;
        // road
        m[r1][k][0] = min(m[r1][k][0], t + roadTime[i]);
        // flight
        int k1 = k+(1-b);
        if (k1 <= K)
          m[r1][k+1-b][1] = min(m[r1][k+1-b][1], t + flightTime[i]);
      }
    }

    ll minimum = LONG_LONG_MAX;
    rep(k,K+1) rep(b,2) minimum = min(minimum, m[N%2][k][b]);

    return minimum;
  }
};

• passed system test