Hatena::Grouptopcoder

hotpepsiの練習帳

2012-10-24

Codeforces 142 Div2

23:46

A. Dragons

問題

  • 自分の腕力sよりも弱いドラゴンは倒せる
  • ドラゴンを倒すと腕力がy増える
  • n匹のドラゴンが倒せるかどうかを求める

方針

  • ソートして足していくだけ

B. T-primes

問題

  • 約数がちょうど3つかどうかを判定する

方針

  • 素数の2乗ならOK
  • 初期化時にstd::set<long long>に突っ込んでおく

C. Shifts

問題

  • N行M列のビット列が与えられる
  • ある列全てを1にするための最小のシフト回数を求める

方針

  • ある行yについて処理することを考える
  • その行yを位置xに揃えるコストを求める
  • ある位置currentにビットが立っていたら、その前にビットが立っている位置prevとcurrentの近いほうにシフトするものとして最小コストを計算
  • 全行のコストを足して、一番小さい桁が答え

結果

oox 808pt 620th rating 1629 -> 1555 (-74)

Cは単純にfindと逆の文字列のfindでやったらTLEした。単純すぎた。

ビットが立っている位置を保持しておいて、2分探索なら通りそう。

トラックバック - http://topcoder.g.hatena.ne.jp/firewood/20121024