naoya_t@topcoder

Member SRM471

01:57 |

500解いてて気がついたら接続が切れてた。再ログインしたらSRM471が消えていた。ノーゲームか。

折角250と500は解いたので、書いたコードは晒しておこう。どちらも解き方はすぐに思いついたが実装がさらっと行かずデバッグに時間を取られた。

Easy(250): PrimeSequences

• 最初、√n個の素数を持っといて割って行くのを書いてたけどこれだと最悪ケースで間に合わない。
  • 1000万までの素数を篩っても600msecぐらいで済むのでやっちまえ
• あとはチェーンの長さの計算でバグってて手間取ったりとか恥ずかしい
  • 2以外の素数は奇数なので2ずつステップしたいところだけど境界条件でバグりやすい
• 結局デバッグで時間とられて投稿までに30分かけてないか？
• 投稿したやつ：

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

class PrimeSequences {
  vector<int> primes; int pn;
  char *is_prime;
  int prepare_primes_until(int till) {
    is_prime = (char *)malloc(1+till);
    if (!is_prime) return -1;
    memset((void*)is_prime, 1, 1+till);
    primes.clear();

    for (int i=2; i<=till; i++){
      if (is_prime[i]) {
        primes.push_back(i);
        for (int j=i*2; j<=till; j+=i) is_prime[j] = false;
      }
    }
    return primes.size();
  }

 public:
  PrimeSequences(){
    pn = prepare_primes_until(10000001);
  }
  ~PrimeSequences(){
    free((void*)is_prime);
  }
  map<int,int> mm;

 public:
/*
  int prime(int n){
    if(found(mm,n)) return mm[n];
    if(n==1)return mm[n]=0;
    if(n==2)return mm[n]=1;
    if((n&1)==0)return mm[n]=0;
    rep(i,pn){
      int p=primes[i];
      if(n<=p) break;
      if(n%primes[i] == 0) return mm[n]=0;
    }
    return mm[n]=1;
  }
*/
  int len(int x){
    int c=0;
    for (int n=x; n>1; n/=2) {
      if (!is_prime[n]) break;
      c++;
    }
    return c;
  }
  int getLargestGenerator(int N, int D) {
    mm.clear();
    if (N==2) return (D==1?2:-1);
    if ((N&1)==0) N--;
    for(int x=N; x>=3; x-=2) {
      if(len(x) >= D) return x;
    }
    return -1;
  }
};

Medium(500): ThirteenHard

• ダイクストラっぽいんだけど
• 途中のどの区間を取っても13の倍数であってはならない
• 同じ町でのループが可。13の倍数を避けることができるケースがありそう
• ある町への最短所要時間とそこに至る経路でのラップタイムをうまく持ち回りたい
• ラップタイムはmod13の0〜12のどれを経験しているかが分かればよい
• 13成分が検出されたら枝刈り
  • スタート地点の0に気をつけて
• 結局2^13=8192, N=25なので int[25][8192]なDP
• サーバ死んでなかったとしても間に合ってないかも
• コードはBFSで書いてます

#define sz(a)  int((a).size())
#define pb  push_back
#define FOR(var,from,to) for(int var=(from);var<=(to);var++)
#define rep(var,n)  for(int var=0;var<(n);var++)
#define all(c)  (c).begin(),(c).end()
#define tr(c,i)  for(typeof((c).begin()) i=(c).begin(); i!=(c).end(); i++)
#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

class ThirteenHard {
  int n;
  vector<vector<int> > ds, e;
 public:
  int conv(char c){
    if ('A'<=c && c<='Z') return 1+(c-'A');
    else if ('a'<=c && c<='z') return 27+(c-'a');
    else return INF;
  }

  int calcTime(vector <string> city) {
    n=sz(city);
    ds.assign(n,vector<int>(n));
    rep(i,n) rep(j,n) ds[i][j] = conv(city[i][j]);
    rep(i,n) cout << ds[i] << endl;
    e.assign(n,vector<int>(8192,INF));

    vector<iii> q; int ql=0;
    q.pb( cons(0,cons(0,0)) ); ql++;
    for(int i=0; i<ql; i++) {
      int wh=car(q[i]), msk=cadr(q[i]), sm=cddr(q[i]);
      if (sm > 0 && sm % 13 == 0) continue;
      
      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 (sm > 0) msk |= (1 << (sm % 13));
      if (sm >= e[wh][msk]) continue; ////※これ駄目

      e[wh][msk] = sm;
      for(int j=0,m=1; j<n; j++,m<<=1) {
        int d_ = ds[wh][j];
        if (d_ != INF) {
          int sm2 = sm + d_;
          q.pb( cons(j,cons(msk, sm2))); ql++;
        }
      }
    }

    int dmin=INF;
    for(int i=2;i<8192;i+=2) dmin=min(dmin,e[n-1][i]);
    return (dmin == INF)? -1 : dmin;
  }
};

Practice Room

• 250: Passed
• 500: Failed →500再考

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先生）