2009-11-26

SRM453.5 Div1 Easy: MazeMaker

01:23 |

高々2500ノードで、各ノードからのarcは高々50本
ということで、dijkstraで解く方法

#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())

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=N*M, Z=sz(moveRow);

    vector<bool> ok(NM,false);
    rep(r,N)rep(c,M) if(maze[r][c]=='.') ok[M*r + c] = true;
    
    vector<vector<int> > ar(NM,vector<int>(NM,infty));
    int start = M*startRow + startCol;

    rep(ri,N)rep(ci,M){
      int i = M*ri + ci; if (!ok[i]) continue;
      rep(z,Z){
        int rj=ri+moveRow[z], cj=ci+moveCol[z];
        if(0<=rj && rj<N && 0<=cj && cj<M){
          int j = M*rj + cj; ar[i][j]=1;
        }
      }
    }

    pair<vector<int>,vector<int> > res = dijkstra_all(ar, start);
    vector<int> distances = res.first;
    int dmax=0;
    rep(i,NM){
      if (i==start || !ok[i]) continue;
      int d=distances[i]; if (d==infty) return -1;
      if (d>dmax) dmax=d;
    }
    return dmax;
  }
};

dijkstraはスタート地点から他の全ノードへの距離を求めるやつ
predecessor返してるけど使わない（ので消してもいい）

const int infty = INT_MAX;

template <typename T> T infsum(T a, T b){
  return (a == infty || b == infty)? infty : (a + b);
}

template <typename T> pair<vector<T>,vector<int> >
dijkstra_all(const vector<vector<T> >& arclength, int start_v)
{
  int N = arclength.size();

  set<int> S;
  vector<T> distance(N, infty); // inftyは適当な大きな数
  vector<int> predecessor(N, -1);

  S.insert(start_v);
  distance[start_v] = 0;

  rep(v,N){
    if (v == start_v) continue;
    if (arclength[start_v][v] == infty) continue;
    
    distance[v] = arclength[start_v][v];
    predecessor[v] = start_v;
  }

  while (S.size() < N) { // 各点へ
    // find v* from V¥S with distance(v*) = min{distance(v):v from V¥S}
    int v_ = -1;
    T d_ = infty;
    rep(v,N){
      if (found(S,v)) continue;
      if (distance[v] < d_) { d_ = distance[v]; v_ = v; }
    }
    if (v_==-1) break;
    S.insert(v_);

    rep(v,N){ // FOR ALL v from V¥S DO
      if (found(S,v)) continue;
      T d_ = infsum(distance[v_], arclength[v_][v]);
      if (d_ < distance[v]) {
        distance[v] = d_;
        predecessor[v] = v_;
      }
    }
  }

  return make_pair(distance,predecessor);
}

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) 派手に落ちたなー

トラックバック - https://topcoder-g-hatena-ne-jp.jag-icpc.org/n4_t/20091126

		2009/11
日	月	火	水	木	金	土
1	2	3	4	5	6	7
8	9	10	11	12	13	14
15	16	17	18	19	20	21
22	23	24	25	26	27	28
29	30

naoya_t@topcoder

2009-11-26

SRM453.5 Div1 Easy: MazeMaker

SRM453.5

250点: MazeMaker

450点: PlanarGraphShop

1000点: TheAlmostLuckyNumbers

Challenge Phase

System Test