Hatena::Grouptopcoder

blu_rayの日記

2012-02-07

Codeforces Round #105 Div2

| 00:48

本番は出てないです。主に卒論とかあったりして。

A. Insomnia cure

1からdの数値の中で{k,l,m,n}の倍数数えるだけ。

#define rep(i,n) for(int (i)=0; (i)<(int)(n); ++(i))
#define foreach(c,i) for(__typeof((c).begin()) i=(c).begin();i!=(c).end();i++)

int main() {
  vector<int> in(4,0);
  int D;
  while (cin >> in[0]) {
    rep(i,3) cin >> in[i+1];
    cin >> D;
    vector<int> a(D+1, 0);
    rep(i,4) {
      for (int j = in[i]; j <= D; j+=in[i])
        a[j] = 1;
    }
    printf("%d\n", count(a.begin(), a.end(), 1));
  }
  return 0;
}

B. Escape

Vp * x + [お姫様の位置] = Vd * x

を計算する。

#define rep(i,n) for(int (i)=0; (i)<(int)(n); ++(i))
#define foreach(c,i) for(__typeof((c).begin()) i=(c).begin();i!=(c).end();i++)

double Vp, Vd, T, F, C;

int main() {
  while (cin >> Vp) {
    cin >> Vd >> T >> F >> C;
    if (Vp >= Vd) { puts("0"); continue; } // #
    double lb = T * Vp;
    int ans = 0;
    while (1) {
      double x = lb / (Vd - Vp);
      lb += Vp * x;
      if (lb >= C) break;
      lb += Vp * x + Vp * F;
      ++ans;
    }
    printf("%d\n", ans);
  }
  return 0;
}

C. Terse princess

とりあえず出力される数列を1で初期化しといて、0番目の要素を先頭として、

1番目の要素からA個だけ t[i] = t[i-1] + 1

Aの処理が終わった後に、B個だけ t[i] = accumulate(t, t + A+i, 0)

で大丈夫そうですが、

1 2 3 4 5 ...

のように1番目の要素から t[i] = t[i-1] + 1 をやるとAの要素じゃなくてBの要素として考慮されてしまうので、先にBの処理を行ってからAの処理を行うと必要なNが少なくて済む。

#define rep(i,n) for(int (i)=0; (i)<(int)(n); ++(i))
#define foreach(c,i) for(__typeof((c).begin()) i=(c).begin();i!=(c).end();i++)

int N, A, B;

template <class Iterator>
Iterator get_advnaced_itr(Iterator _itr, int n) {
  Iterator itr(_itr);
  advance(itr, n);
  return itr;
}

void print(const vector<int>& vi) {
  rep(i,vi.size()) {
    if (i) putchar(' '); printf("%d",vi[i]);
  }
  puts("");
}

int main() {
  while (cin >> N >> A >> B) {
    vector<int> a(N, 1);
    if (N == 1 || (A == 0 && B == 0)) { print(a); continue; }
    if (2 + A > N) { puts("-1"); continue; }

    for (int i = 0; i < B; ++i) {
      a[1+i] += accumulate(a.begin(), get_advnaced_itr(a.begin(), i+1), 0);
    }

    int endB = 1+B;
    if (endB == 1) ++endB;
    if (endB + A > N) { puts("-1"); continue; }
    for (int i = 0; i < A; ++i) {
      a[endB+i] = a[endB+i-1]+1;
    }
    print(a);
  }
  return 0;
}

D. Bag of mice

なんとなくそれっぽい再帰を書いて、メモ化したら出来た。

掛け合わせるdouble変数がnanとかinfになったりしてつまった。

#define rep(i,n) for(int (i)=0; (i)<(int)(n); ++(i))
#define foreach(c,i) for(__typeof((c).begin()) i=(c).begin();i!=(c).end();i++)

int W, B;
double dp[1002][1002];

double rec(int w, int b) {
  double dw = w, db = b;
  // bounds checking
  if (b == 0) { return w > 0 ? 1 : 0 ; }
  if (w <= 0 || b < 0) return 0;
  if (dp[w][b] >= 0) return dp[w][b];

  double &d = dp[w][b];
  
  // princess chose w
  double pcw = dw/(dw+db);
  // princess chose b
  double pcb = db/(dw+db);
  // dragon chose b
  double dcb = (db-1)/(dw+db-1);
  // espace w, b
  double sw = (dw)/(dw+db-2), sb = (db-2)/(dw+db-2);
  // calc
  d = pcw;
  if (w >= 1 && b >= 2)
    d += pcb * dcb * sw * rec(w-1, b-2);
  if (w > 0 && b >= 3)
    d += pcb * dcb * sb * rec(w, b-3);
  // debug
  if (isnan(dp[w][b])) {
    printf("%d:%d %lf %lf %lf %lf %lf\n", w, b, pcw, pcb, dcb, sw, sb);
    printf("%lf %lf\n", dp[w-1][b-2], dp[w][b-3]);
    assert(false);
  }
  return d;
}

int main() {
  while (cin >> W >> B) {
    if (W == 0) { puts("0"); continue; }
    memset(dp, -1, sizeof dp);
    printf("%.9lf\n", rec(W, B));
  }
  return 0;
}

E. Porcelain

適当に状態を考えると

[i][l][r][m] => [100][100][100][10000] := 叫んだ回数がm回で、i番目の本棚の陶磁器が左からl個壊れて右からr個壊れている状態

のような、やばい状態数が考えられますが、

1番目の棚の左端が壊れる事と2番目の棚の右端が壊れる事のような、異なる棚での陶磁器が壊れる現象はどちらが先に起きても問題ないので、(陶磁器の壊れる順番が大事なのは、それぞれの棚における端から壊れるということだけ)

棚同士の状態は分けて考えることが出来て、i番目の本棚でm回叫んだ時の破壊できる陶磁器の価値の和の最大値を求めて、それを利用して求めつづけるのをやったら通った。

一番大きなループが最大ケースで、100 * 100 * 10000 くらいあってTLEすると思ったけど、なんか実行時間330msで通った。

#define rep(i,n) for(int (i)=0; (i)<(int)(n); ++(i))
#define foreach(c,i) for(__typeof((c).begin()) i=(c).begin();i!=(c).end();i++)

const int kMaxM = 10002, kInf = 1 << 30;
int N, M;
int ns[102], a[102][102];
int dp[2][10002];

int main() {
  while (cin >> N >> M) {
    rep(i,N) {
      cin >> ns[i];
      rep(j,ns[i]) cin >> a[i][j];
    }
    rep(i,2) fill(dp[i], dp[i] + kMaxM, -kInf);
    dp[0][0] = 0;
    int *prv = dp[0], *nxt = dp[1];
    rep(i,N) {
      vector<int> dp2(kMaxM, 0);
      // calc
      for (int l = 0; l <= ns[i]; ++l) {
        for (int r = 0; l + r <= ns[i]; ++r) {
          int um = l + r;
          int v = accumulate(a[i],a[i]+l,0) +
                  accumulate(a[i]+ns[i]-r,a[i]+ns[i],0);
          dp2[um] = max(dp2[um], v);
        }
      }
      // update
      for (int j = 1; j <= ns[i]; ++j) {
        const int add = dp2[j];
        for (int k = 0; k <= M; ++k) {
          if (k-j >= 0)
            nxt[k] = max(nxt[k], max(prv[k], prv[k-j] + add));
          else
            nxt[k] = max(nxt[k], prv[k]);
        }
      }
      swap(prv, nxt);
    }
    printf("%d\n", prv[M]);
  }
  return 0;
}