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再考