hotpepsiの練習帳

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はあとで解く。