hotpepsiの練習帳

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分探索なら通りそう。