naoya_t@topcoder

SRM458

SRM | 02:57 |

01.14.2009+

DIV	level	問題名	競技中	後で	System Test	通過率	備考
1	250	BouncingBalls	15'45''	-	passed system test	-	196.42pt
1	450	NewCoins	間に合わず	-	-		-
1	900	-	開いてない				-

250点問題: BouncingBalls

• すべてのパターンについて調べても高々2^12通り
• 跳ね返る回数＝跳ね返らず直進するとした場合に交差する回数
• 傾きが同じなら除外
• 交点が(0..t]にあるか
• 15'45''
• passed system test

#define sz(a)  int((a).size())
#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++)

class BouncingBalls {
  vector<int> y,v;
  int n,t;
  int test(){
    int cnt = 0LL;
    for(int i=0;i<n-1;i++){
      for(int j=i+1;j<n;j++){
        if (v[i]==v[j]) continue;
        double at = (double)(y[j] - y[i])/(v[i] - v[j]);
        if (0 < at && at <= t) cnt++;
      }
    }
    return cnt;
  }
 public:
  double expectedBounces(vector<int> x, int T) {
    n=sz(x); t=T;
    y.assign(all(x)); v.resize(n);
    int ps=1<<n, cnt=0;
    rep(p,ps){
      for(int j=0,m=1;j<n;j++,m<<=1) v[j] = (p&m) ? 1 : -1;
      cnt += test();
    }
    return (double)cnt / ps;
  }
};

450点問題: NewCoins

• Sample Caseが全部通るやつは書けた。まだ30分ちょい残ってる。
• でも最悪とは言えないまでもひどいケースで試してTLE
• これがなんとかならないとsubmitできない
• なんとかならなかった
• 提出を諦めた（Sample Caseしか通らない）コードを晒しておく：

#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> i_i;

class NewCoins {
  int n,maxprice;
  vector<i_i> av; int avn;
  vector<int> coins;

  map<vector<int>,int> memo;
  map<vector<int>,int> mmc;

  int sub() {
    int cn = sz(coins); 

    if (found(memo,coins)) return memo[coins];
    
    int lastcoin = coins.back(); coins.pop_back();

    int cntnow=0;
    if (found(mmc,coins)) {
      cntnow = mmc[coins];
      coins.pb(lastcoin);
      rep(i,avn){
        if (av[i].first>=lastcoin){
          int k = (av[i].first / lastcoin) * av[i].second;
          int m = lastcoin / coins[cn-2];
          cntnow -= (m-1)*k;
        }
      }
    } else {
      // cn=1
      coins.pb(lastcoin);
      rep(j,avn){
        if (av[j].first % lastcoin) {
          memo[coins]=-1; return -1;
        }
        cntnow += av[j].second * av[j].first/lastcoin;
      }
    }

    mmc[coins] = cntnow;
    cn++;

    for(int b=lastcoin*2;b<=maxprice;b+=lastcoin){
      coins.pb(b);
      int cnt = sub();
      coins.pop_back();
      if (cnt >= 0) cntnow = min(cntnow, cnt);
    }
    memo[coins] = cntnow;
    return cntnow;
  }
 public:
  int minCoins(vector<int> price) {
    memo.clear();
    mmc.clear();
    n=sz(price); maxprice = price[n-1];
    map<int,int> a;
    rep(i,n) { int p=price[i]; if (found(a,p)) a[p]++; else a[p]=1; }
    av.assign(all(a)); avn = sz(av);
    if (avn==1) return av[0].second;

    int minc=INT_MAX;
    coins.clear();
    for(int b=1;b<=price[0];b++){
      coins.pb(b);
      int cnt = sub();
      coins.pop_back();
      if (cnt >= 0) minc = min(minc, cnt);
    }
    return minc;
  }
};

900点問題: 開いてない

Challenge phase

• 他の人の450を見てみた。Javaが多い。あと、なんか短い。

System Test

o - -

196.42 points

結果

room:9/20位

DIV1:282/680位

1292→1366(+74) 少し持ち直したがまだ青。