ABC 141 D - Powerful Discount Tickets 解説

問題: D - Powerful Discount Tickets

問題概要

$N$ 個の商品の値段 $A_1, A_2, \dots, A_N$ と割引券の枚数 $ M $ が与えられる。$a$ 円の商品に $b$ 枚割引券を使うと $\lfloor a / 2^b \rfloor$ 円で買える。$N$ 個の商品をすべて買うために必要な金額の最小値を求めよ。

解法

まず、割引券をまとめて使うのと「$1$ 枚ずつ使う」のは同じです。つまり $\lfloor a / 2^b \rfloor = \lfloor \cdots \lfloor\lfloor\lfloor a / 2 \rfloor / 2 \rfloor \cdots \rfloor / 2 \rfloor$ です。これは任意の非負整数 $a$ と任意の正整数 $p, q$ に対して $\lfloor a / (pq) \rfloor = \lfloor \lfloor a / p \rfloor / q \rfloor$ が成り立つ *1 ことから帰納的にわかります。

そこで、次を $ M $ 回繰り返せば最適解を求められそうな気がします。

現時点で最高値の商品の値段を $1/2$ にする ($\diamond$)

実際にこれが最適であることを証明しましょう。

証明

なにはともあれ、求めたいものを式で表すことから始めます。
商品 $i$ に割引券を $Y_i$ 枚使うとします。このとき、$N$ 個の商品をすべて買うために必要な金額は $\sum_{i = 1}^N \lfloor A_i / 2^{Y_i}\rfloor$ です。これを $f(Y)$ とおきます。$Y$ が $\sum_{i = 1}^N Y_i = M $ を満たしながら動くときの $f(Y)$ の最小値を求めたいです。
($\diamond$) を実行した結果わかる割引券の配分を $B$ としましょう。商品 $i$ の値段を $B_i$ 回 $1/2$ にした、商品 $i$ に $B_i$ 枚割引券を使った、という意味です。$B$ が最適解であるとは、他のどんな割引券の配分よりも $f(B)$ が小さい (か同じである) ことです。

任意に割引券の配分をひとつ固定します。これを $C$ とします。 $f(C) \ge f(B)$ を示したいです。$C = B$ ならば明らかに成り立つので $C \not= B$ とします。
簡単のために

• $B_1 > C_1$
• $B_2 < C_2$

だとします。このとき $C' := (C_1 + 1, C_2 - 1, C_3, \dots, C_N)$ とおくと $f(C) \ge f(C') $ ($\star$) です。$C' = B$ ならば $f(C) \ge f(B)$ となり終わりです。$C' \not= B$ ならば同様のことを繰り返して $f(C) \ge f(C') \ge f(C'') \ge \dots \ge f(C^{\prime\prime\cdots\prime}) = f(B)$ が得られるので OK です。

($\star$) の証明

おおよそ次のような感じです。

• 商品 $1$ が最高値のときに使える割引券がない
• → 商品 $2$ に使っていた分の割引券を $1$ 枚持ってきて代わりに使う
• → そのとき最終的に支払う合計金額は悪化しない

割引券を使う順番を $(\diamond)$ に沿うようにしてみます。
すると $B_1 > C_1$ より、最高値の商品を半額にするのを見逃してしまうタイミングがあります。正確には、

• 商品 $1$ が現時点で最高値
• これまでで、商品 $1$ に割引券を $C_1$ 枚使った (もう使える割引券がない)

というタイミングがあります。これが $t$ 回目に割引券を使う機会だとします。また、このときの

• 商品 $1$ の値段: $x$ 円
• 商品 $2$ の値段: $y$ 円

だとします。$x \ge y$ です。$t$ 回目以降の割引券を使う順番は、基本的にてきとうでよいですが最後 ($M $ 回目) は商品 $2$ に割引券を使うようにします。$B_2 < C_2$ なので商品 $2$ に使える商品券は時刻 $t$ の時点で少なくとも $1$ 枚余っていますから、これを取っておきましょう。

商品 $2$ に対する割引券がたくさん余ってる ($C_2$ が大きい) 状況を考えると、最後の割引券を使う直前で、商品 $2$ の値段は $\lfloor y / 2^k \rfloor$ の形をしています。これを $z$ とします。$y \ge z$ です。$M $ 回目は商品 $2$ に割引券を使うので、最終的には $\lfloor z / 2\rfloor$ 円になります。

商品ごと・時刻ごとの値段を表にしました。

全商品合計で割引券を使った回数 ＼ 商品	$1$	$2$
$t - 1$	$x$	$y$
$M - 1$	$x$	$z$
$M $	$x$	$\lfloor z/2 \rfloor$

割引券の配分が $C$ のとき・$C'$ のときに支払う合計金額を比べましょう。配分が $C'$ のときは

• $1$ 回目 ～ $M - 1$ 回目に使う割引券: 配分が $C$ のときと同じ商品に対して使う
• $M $ 回目に使う割引券: 商品 $1$ に対して使う

とします。このとき

• $f(C) = \sum_{i = 1}^N \lfloor A_i / C_i\rfloor = \sum_{i = 3}^N \lfloor A_i / C_i\rfloor + x + \lfloor z / 2 \rfloor$
• $f(C') = \sum_{i = 1}^N \lfloor A_i / C'_i\rfloor = \sum_{i = 3}^N \lfloor A_i / C_i\rfloor + \lfloor x / 2 \rfloor + z$

ですから、$f(C) - f(C') = \lceil x / 2\rceil - \lceil z / 2 \rceil \ge \lceil x / 2\rceil - \lceil y / 2 \rceil \ge 0$ となり、$f(C) \ge f(C')$ がわかりました。

類題

この問題 も似た流れで証明できると思います。

*1:証明は AtCoder 公式の解説 PDF https://img.atcoder.jp/abc141/editorial.pdf を見てください