naoya_t@topcoder

SRM453.5

02:54 |

11.25.2009+

.5って何さ

DIV	level	問題名	競技中	後で	System Test	通過率	備考
1	250	MazeMaker	o	-	failed		0
1	450	PlanarGraphShop	撃墜された	-	-		-
1	1000	TheAlmostLuckyNumbers	間に合わず				-

250点: MazeMaker

• 撃墜は免れたがfailed system test...
  • TLE
  • 教訓。
  • 幅優先なところでpriority_queueとか書いてるとはまる
  • ダイクストラで解ける？と思って後で書いたら速かった。
• 以下、投稿した恥コード：
  • carとかcadrとかマクロあると非常に便利

#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> i_i;
typedef pair<int,pair<int,int> > i_ii;
#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

class MazeMaker {
 public:
  int longestPath(vector <string> maze, int startRow, int startCol, vector <int> moveRow, vector <int> moveCol) {
    int N=sz(maze), M=sz(maze[0]), NM=0, Z=sz(moveRow);
    rep(r,N)rep(c,M) if(maze[r][c]=='.')NM++;
    priority_queue<i_ii> pq;
    vector<vector<int> > vd(N,vector<int>(M,INT_MAX)); int vdc=0;
    pq.push(cons(0,cons(startRow,startCol)));
    while(!pq.empty()){
      i_ii t = pq.top(); pq.pop();
      int i=-car(t), r=cadr(t), c=cddr(t);
      if (maze[r][c]=='X') continue;
      if (vd[r][c]<i) continue;
      if (vd[r][c]==INT_MAX) vdc++;
      vd[r][c]=i;
      if (vdc == NM) break;
      rep(z,Z){
        int r2 = r + moveRow[z]; if (r2 < 0 || N <= r2) continue;
        int c2 = c + moveCol[z]; if (c2 < 0 || M <= c2) continue;
        pq.push(cons(-(i+1),cons(r2,c2)));
      }
    }
    if (vdc < NM) return -1;
    int mx=0;
    rep(r,N)rep(c,M) {
      if (vd[r][c]==INT_MAX) continue;
      if (vd[r][c]>mx)mx=vd[r][c];
    }
    return mx<INT_MAX ? mx : -31;
  }
};

• 後で書いた、ちゃんと通るコードは別エントリにて

450点: PlanarGraphShop

• 投稿コード：

#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 FOR(var,from,to) for(int var=(from);var<=(to);var++)
#define RFOR(var,from,to) for(int var=(to);var>=(from);var--)
#define found(s,e)  ((s).find(e)!=(s).end())

class PlanarGraphShop {
  vector<int> xs; int xsn;
  vector<int> m,m0;
  
  int cost(int v, int e){
    return v*v*v + e*e;
  }
  int sub(int n){
    if(m[n]<INT_MAX) return m[n];
    priority_queue<int> pq;
    tr(m0,it){
      int x=*it; if(x>n) continue; if(x==n)return 1;
      pq.push(-(1+m[n-x]));
    }
    return -pq.top();
  }
 public:
  int bestCount(int N) {
    double r = pow((double)N, 1.0/3);
    int rc = (int)floor(r + .00001);

    set<int> cs;
    FOR(n,1,rc){
      FOR(e,0,max(0,n*2-3)){
        int c=cost(n,e);
        if(c>N) continue;
        if(c==N) return 1;
        cs.insert(c);
      }
    }
    xs.assign(all(cs)); xsn=sz(xs);
    m0.clear();
    m.resize(N+1); FOR(i,0,N) m[i]=INT_MAX;
    tr(xs,it) { m0.pb(*it); m[*it]=1; }

    FOR(i,1,N){
      if (m[i] < INT_MAX) continue;
      m[i] = sub(i);
    }
    return m[N];
  }
};

• 撃墜される
  • はい。n*2-3て何ですか
  • 教訓：planar graphとかぐぐればよかったのに（wikipediaに載ってる！！！）
  • n*2-3 を n>=3でn*3-6 にするだけで通った

1000点: TheAlmostLuckyNumbers

• そんなに難しい問題にも見えない（けど時間ない）
• 時間ないとか書いてるけど、途中まではコード書いたんだからね
• て３問目までコード書いてたの初めてかも
• 4,7,44,47,74,77,...という数列
  • これらの倍数の数を数えればいい
  • Inclusion-exclusion principle
  • 44とか4の倍数だから捨ててもいいっしょ
  • とかその辺りまで

class TheAlmostLuckyNumbers {
  vector<ll> lns; int lnsn;
  
  int keta(ll x){
    if(x<10) return 1;
    return 1+keta(x/10);
  }
  ll rp(int k,int mask){
    ll r=0, b=1LL;
    for(int i=0,m=1;i<k;i++,m<<=1){
      r += b * ((mask&m)? 7 : 4);
      b *= 10LL;
    }
    return r;
  }
  ll sub(ll x){
    if(x==0) return 0;

    int k=keta(x);

    ll cx=0;
    rep(i,lnsn){
      cx += x / lns[i];
    }
    printf("sub(%lld:%d) <= %lld\n", x,k, cx);

    return cx;
  }
 public:
  long long count(long long a, long long b) {
    lns.clear();
    for(int k=1;k<=10;k++){
      for(int m=0;m<1<<k;m++){
        ll r = rp(k,m); if (r>b) break;
        int skip=0;
        rep(i,sz(lns)) if (r%lns[i]==0) skip=1;
        if(!skip) lns.pb(r);
      }
    }
    lnsn = sz(lns);
    cout << lnsn << " " << lns << endl;
    ll x=1LL; int f=lnsn;
    rep(i,lnsn){
      x *= lns[i]; if(x>b){ f=i; break; }
    }
    printf("s1.size = %d\n", lnsn);

    // ... この辺りまで 

    return sub(b) - sub(a-1);
  }
};

• きなばさんが投稿に３秒足りなかったらしい

Challenge Phase

• 450点轟沈

System Test

• 250点Failed System Test
• 毎度ながら赤い字がどきっとする

0点...

1518→1359 (-159) 派手に落ちたなー