Hatena::Grouptopcoder

blu_rayの日記

2011-09-15

SRM 518 Div2

| 18:29

oo-

250. TwiceString / Passed System Test / 175

Easyに面喰らう事が多い。

あれこれ迷いながら、1文字ずつずらして重なるか見るに着地。時間掛かった。

500. LargestSubsequence / Passed System Test / 411

Easyの方が難しいと思った。

文字列の中で最大の文字を見つけて、解に追加して、

発見した位置より右の範囲で再び最大の文字を見つけて、解に追加して、・・を繰り返すだけ。

1000. CoinReversing / Opened / 0

通してる人が多くて、コードも短めの人が多いので、出来る人には簡単だったっぽい。

本番中はTLEするような方法しか思いつかなかった...大体下記の方法がわかりやすかった。

E ≡ 期待値, prevE ≡ 一つ前の期待値
A ≡ 表向きのコインの選択される枚数期待値, B ≡ 裏向きのコインの選択される枚数期待値
(0 .. K-1).each do |i|
  A = a[i] / N * prevE
  B = a[i] - A
  E = prevE - A + B
  prevE = E
end

初期状態のprevEをNとして、その場の期待値を順番に求めていく事で最終的な答えが出る。。。

rate := 954 -> 963