naoya_t@topcoder

SRM459

03:12 |

01.19.2009+

DIV	level	問題名	競技中	後で	System Test	通過率	備考
1	250	Inequalities	17'05''	-	passed system test	-	190.19pt
1	500	NumberPyramids	間に合わず	-	-		-
1	1000	-	開いてない				-

Easy: Inequalities

• test case#0が通らない
  • どこかバグってるのかな（ここで割と悩む
• あ。問題読み違えてた。離散的にしか見てなかった
  • 0.5ずつ見ればいけるね
• おｋ
• 190.19pt (17'05'') 時間かかりすぎorz
• 恥コード晒し
  • 関数分ける意味あまりない。タイプ量の無駄遣い

enum { LT=0,LE,EQ,GE,GT };
char* ops[] = {"<","<=","=",">=",">"}; // for debug

class Inequalities {
 public:
  int s2op(string s){
    if(s=="<") return LT;
    if(s=="<=") return LE;
    if(s=="=") return EQ;
    if(s==">=") return GE;
    if(s==">") return GT;
  }
  bool fulfill(double x,int op,int e) {
    switch(op) {
      case LT: return (x < e); break;
      case LE: return (x <= e); break;
      case EQ: return (x == e); break;
      case GE: return (x >= e); break;
      case GT: return (x > e); break;
    }
  }
  int maximumSubset(vector <string> inequalities) {
    vector<pair<int,int> > ineq;
    
    int n=sz(inequalities);
    rep(i,n){
      vector<string> ar=split(inequalities[i]);
      ineq.pb(make_pair(s2op(ar[1]),atoi(ar[2].c_str())));
    }
    
    int mmm=0;
    for(double j=-1;j<=1001;j+=0.5) {
      int cnt=0;
      tr(ineq,it){
        if (fulfill(j,it->first,it->second)) {
          cnt++;
        }
      }
      if (cnt != 0 && cnt>mmm) mmm = cnt;
    }
    return mmm;
  }
};

Medium: NumberPyramids

• サンプルケースが通るやつは割とさらっと書けた
  • しかし19段の追加ケースとかTLE
  • メモ化いろいろ考えたけど解決できず
  • 終了
• Challengeで2人投稿してるのを見たら割とシンプルに書いてあった...
• TLEコード晒す

typedef long long ll;
#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())

ll MOD = 1000000009LL;

class NumberPyramids {
  int n,am;
  vector<int> z,k;
  vector<map<int,int> >memo;
  
  int sub(int rest,int till) {
    if (rest < 0) return 0;
    if (found(memo[till],rest)) return memo[till][rest];

    ll cnt = 0LL;
    
    if (till==0) {
      cnt = rest + 1;
    } else {
      int b=z[till],mx=rest/b;
      FOR(i,0,mx) {
        if (k[till]==1)
          cnt += sub(rest-b*i,till-1);
        else
          cnt += (1LL+i) * sub(rest-b*i,till-1);
      }
    }
    return memo[till][rest] = cnt % MOD;
  }
      
 public:
  int count(int baseLength, int top) {
    if (baseLength==2) return top-1;
    if (baseLength>19) return 0;

    memo.resize(11);
    rep(i,11) memo[i] = map<int,int>();
    
    vector<vector<int> > a(2,vector<int>(baseLength,0));
    a[0][0] = a[0][1] = 1;
    int sum;
    FOR(i,2,baseLength-1){
      int i0 = i%2, i1 = (i+1)%2;
      sum = a[i1][0] = a[i0][0];
      FOR(j,1,i) {
        sum += (a[i1][j] = a[i0][j-1] + a[i0][j]);
        if (sum > top) return 0;
      }
    }
    int rest = top - sum;
    if (rest == 0) return 1;

    ///※
    n = (baseLength + 1)/2;
    z.resize(n); k.resize(n);
    rep(i,n) { z[i]=a[baseLength%2][i]; k[i]=2; }
    am = baseLength & 1; if(am) k[n-1]=1;

    return (int)(sub(rest,n-1) % MOD);
  }
};

• 【追記】※以降の部分は

    vector<ll> dp(rest+1,0LL); dp[0]=1;
    tr(a[baseLength%2],it){
      FOR(i,*it,rest) dp[i] = (dp[i] + dp[i-*it])%MOD;
    }
    return dp[rest];

ですんなり行けるっぽい… こういうのがさらっと出てこないと駄目だな

Hard: 開いてない

Challenge Phase

• Easyは全員。Mediumは2人だけ。Hardは皆無
• 誰も落ちない

System Test

• Easy割と落ちてる人がいる。黄色とか赤とかでも割と。
• 自分のは大丈夫だった

o - -

190.19points

結果

room:11/20位

DIV1:380/694位

1366→1392(+26) まだまだ青い。これは恥ずかしくて外を歩けない。