Hatena::Grouptopcoder

hotpepsiの練習帳

2013-01-14

Codeforces 160

16:32

Div2 A. Roma and Lucky Numbers

問題

  • 4と7がラッキーナンバー
  • 4と7がk個までの数の個数を求める

方針

  • 数えるだけ
  • intではなくstringで入力する

Div2 B. Roma and Changing Signs

問題

  • 非減少の数列が与えられる
  • ちょうどk回符号を反転する
  • 和の最大値を求める

方針

  • 最後の負の数までは、小さいほう(絶対値の大きいほう)から反転していく
  • 最後の負の数については、正の数を反転したほうが良いケースがある
  • 場合わけ...
  • (終了後)
  • 絶対値でソートして持っておくのもあり

Div2 C. Maxim and Discounts

問題

  • スーパーで買い物をする
  • Mパターンの割引がある
  • まとめて買うと割引される
  • 割引するためにはq個買う
  • q個の中の最低金額を上回らない品物が最大2個無料になる

方針

  • DPかな
  • 提出
  • TLE...
  • 総和をいちいち求めていたので、差にする
  • 提出
  • TLE...
  • これ大きな個数の割引は無視して良いのでは
  • 提出

結果

ooo-- 00:05+0,00:45+2,01:29+2 2076pt 444/1424 rating 1581 -> 1534

Bはとりあえず負の数は全部反転させて、そのあと絶対値の判定をすればよかった。最後のインデックスの負数で場合わけしてしまい複雑になった。

Cは最小のだけ貪欲に適用すればよかった。

Dはあとで解く。

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