SRM 582

不参加してました。1981->1804 さすがに適正レートとは思えないけど、一回ミスると激落ちするTCの仕様上、本当に上がりにくい。つらい。

250

概要：魔法少女たちの強さと各種類の敵の強さと個体数が与えられるので、魔法少女１人が倒す敵の数の最大値を最小化せよ。
解法：最大値を最小化とか二分探索して下さいと言っているようなものなので、とりあえず思考停止で二分探索書く。

P e[MX], f[MX];
long long minimalFatigue(vector <int> s, vector <int> es, vector<long long> cnt) {
  int n = s.size(), m = es.size();
  ll l = -1, r = (ll)INF*INF, c;
  int t; ll g;
  rep(i,m) e[i] = P(es[i],cnt[i]);
  sort(e,e+m); sort(rng(s));
  while(l+1<r){
    c = (l+r)/2;
    t = m-1;
    rep(i,m) f[i] = e[i];
    drep(i,n){
      g = c;
      while(t >= 0 && g > 0){
        if(f[t].fi > s[i]) break;
        if(f[t].se > g){
          f[t].se -= g;
          break;
        } else {
          g -= f[t].se;
          t--;
        }
      }
    }
    if(t == -1) r = c; else l = c;
  }
  if(r == (ll)INF*INF) r = -1;
  return r;
}

上限を(2*10^7)^2にしててしんだ。あほすぎ・・・

600

概要：高さが1~Nで色がc[1]~c[N]のビルを１列に並べて、見えるビルがL個になるのは何通りか。ただし「見える」とはあるビルの前にそれより高いビルがなくてかつ、ひとつ前の見えるビルと異なる色であること。
解法：
高さがNのビル->1のビルの順でビルを置いていく。i番目(1番目は高さNってこと)のビルをおく場所は現在一番前にあるビルの前かそれより後ろの好きな位置の合計i箇所ある。
dp[i][j] = i番目までのビルを並べた時にj個ビルが見える時の場合の数
色がなければこれだけで解けるが、色があるので、
prev[i] = i番目のビルと同じ色でi番目のビルより高いもののうち最も近いもの
pdp[i][j] = i番目のビルと同じ色のビルが先頭にある時のdp[i][j]
も計算しておけば良い。
（計算の過程で階乗modとそれの逆元が必要になるのでそれも計算しておく。）

ll f[MX], g[MX];
int c[MX], pre[MX];
int pid[MY];
ll dp[MX][MX], d[MX][MX];

class ColorfulBuilding {
  public:
  ll jo(ll x, int t){
    ll res = 1;
    while(t){
      if(t&1) res = (res*x)%mod;
      x = (x*x)%mod;
      t >>= 1;
    }
    return res;
  }
  int count(vector <string> c1, vector <string> c2, int l) {
    int n = 0, x;
    char ch;
    rep(i,c1.size()){
      rep(j,c1[i].size()){
        ch = c1[i][j];
        if(ch >= 'a' && ch <= 'z'){
          c[n++] = (ch-'a')*52;
        } else {
          c[n++] = (ch-'A'+26)*52;
        }
      }
    }
    n = 0;
    rep(i,c2.size()){
      rep(j,c2[i].size()){
        ch = c2[i][j];
        if(ch >= 'a' && ch <= 'z'){
          c[n++] += (ch-'a');
        } else {
          c[n++] += (ch-'A'+26);
        }
      }
    }
    f[0] = 1;
    rrep(i,n) f[i] = f[i-1]*i%mod;
    g[n] = jo(f[n],mod-2);
    drep(i,n) g[i] = g[i+1]*(i+1)%mod;
    
    rep(i,MY) pid[i] = -1;
    reverse(c,c+n);
    rep(i,n){
      pre[i] = pid[c[i]];
      pid[c[i]] = i;
    }
    rep(i,n)rep(j,l+1) d[i][j] = 0;
    rep(i,n)rep(j,l+1) dp[i][j] = 0;
    
    dp[0][1] = 1;
    d[0][1] = 1;
    
    ll nd, sd, dd;
    
    rrep(i,n-1){
      x = pre[i];
      rrep(j,l){
        nd = dp[i-1][j];
        if(x == -1) sd = 0; else{
          sd = ((d[x][j]*f[i-1])%mod*g[x])%mod;
        }
        dd = (nd-sd+mod)%mod;
        dp[i][j] += dd*i+sd*(i+1);
        dp[i][j] %= mod;
        dp[i][j+1] += dd;
        dp[i][j+1] %= mod;
        d[i][j+1] += dd;
        d[i][j+1] %= mod;
        d[i][j] += sd*(i+1);
        d[i][j] %= mod;
      }
    }
    
    return dp[n-1][l];
  }
}

ムダにあわてて書いたからいろんな場所がバグってた。落ち着け・・・