Codeforces 26 - kozima の雑記

参加しました。今回は新しいルールということで，lock と hack という仕組みが導入されました。システムとしては topcoder の SRM に近くなっているようです。

A. Almost prime numbers

相異なる素因数をちょうど二つもつ正の整数を almost prime number といいます。与えられた n に対して，1 以上 n 以下の almost prime number の個数を計算しましょう。

素数リスト生成してなんかごにょごにょやればできるんだろうなー，とか最初は思ったけど n <= 3000 とか書いてあるので almost prime number のリストを xyzzy で計算して埋め込みました。答えのリストを埋め込んでもよかったですね。

で，後で考えると素数リストなんか生成する必要なくて，直に篩で解けます。

int main () {
  int a[3001], n, i, j, c = 0;
  scanf("%d", &n);
  for (i = 0; i <= n; i++) a[i] = 0;
  for (i = 2; i <= n; i++) {
    if (a[i] == 0) for (j = i; j <= n; j += i) a[j]++;
    if (a[i] == 2) c++;
  }
  printf("%d\n", c);
  return 0;
}

F# だとこんな感じ？あんまりきれいになりませんね。

let solve n =
  let a = Array.create (n+1) 0 in
  let rec f i c =
    if i > n then c else
      match a.[i] with
        | 0 -> sieve i; f (i+1) c
        | 2 -> f (i+1) (c+1)
        | _ -> f (i+1) c
  and sieve p =
    for k = 1 to n/p do a.[k * p] <- a.[k * p] + 1 done
  in if n < 2 then 0 else f 2 0

B. Regular Bracket Sequence

マッチしてたりしてなかったりする括弧の列があります。いくつか消して全部マッチしてるようにします。最大で何個残せますか。

最初の状態で対応するものがない括弧だけ除けば通りました。入力がちょっと大きいので DP で。

C. Parquet

タイルの詰め込み。長方形の領域に，与えられた個数の 1x2, 2x1, 2x2 のタイルを敷き詰める。よくわからない。

D. Tickets

チケットを売ります。10 ユーロです。10 ユーロ持って買いにくる人が n 人，20 ユーロ持って買いに来る人が m 人います。お釣り用に 10 ユーロ札が k 枚あります。お客の m+n 人がランダムな順番で来るとき，全員におつりを払える確率はいくらでしょうか。

m >= k のときは 1，n + k < m のときは 0 で，それ以外のときは

$p(n, m, k) = \frac{1}{m+n} (n \cdot p(n-1, m, k+1) + n \cdot p(n, m-1, k-1))$

だと思いますが，これだと TLE なので*1頑張って計算して

$1 - \frac{(m-k) \cdots m}{(n+1) \cdots (n+1+k)}$

を出します。k は小さいのでそのまま計算できます。

たぶん上の漸化式からこれを見つけるのは大変なので，おつりの払えないパターンが全部でいくつあるかを計算したほうがいいでしょうけど。説明省きますが答えは $\left({m+n \atop k+n+1}\right)$ になります。

*1:ちなみに，これをそのまま書いてる人がいたので hack 仕掛けたら落ちた