Hatena::Grouptopcoder

naoya_t@topcoder RSSフィード

2010-04-22

SRM468 Medium: RoadOrFlightHard

| 23:50 | SRM468 Medium: RoadOrFlightHard - naoya_t@topcoder を含むブックマーク はてなブックマーク - SRM468 Medium: RoadOrFlightHard - naoya_t@topcoder SRM468 Medium: RoadOrFlightHard - naoya_t@topcoder のブックマークコメント

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
トラックバック - http://topcoder.g.hatena.ne.jp/n4_t/20100422