ARMERIA

Rubyと競技プログラミングの話 AtCoderやCodeforcesの問題解説記事が多め。

HUPC2019 Day1 D: 貪欲が最適?

お題箱より。

Aizu Online Judge Arena

解法

答えとなる金額の払い方の必要条件を考える

ある金額  x について貪欲な払い方よりも真に枚数が少ない払い方が存在することを、単に「金額  x は条件を満たす」と書くことにします。そして条件を満たす最小の金額(答え)が存在すると仮定して、それを  X 円と表記します。

答えとなる  X 円の払い方について必要条件を考えてみると、実は意外と絞れることに気づきます。まず、

  •  X 円の貪欲な払い方は、 B 円硬貨を必ず含む

ということが言えます。つまり必ず  X \ge B であるということです。もしそうでない場合使える硬貨は  A 円と  1 円だけになり、これでは貪欲が必ず最適になるからです。

このことからさらに、

  •  X 円の最適な払い方は、 B 円硬貨を必ず含まない

ということも言えます。もし条件を満たす  X に対する貪欲な払い方と最適な払い方にともに  B 円硬貨が含まれている場合、その硬貨を取り除くことで  X-B も条件を満たすことが分かるからです。これでは  X が条件を満たす最小値だという仮定に反します。

そうすると最適な払い方について

  •  X 円の最適な払い方は、 A 円硬貨を必ず含む

ことも言えます。もし含まない場合最適な払い方で使える硬貨が1円だけになってしまい、これで貪欲に勝つことはできません。そうすると先ほどと同様の理由で

  •  X 円の貪欲な払い方は、 A 円硬貨を必ず含まない

ことも言えます。

さらにもうひとつ、

  •  X 円の最適な払い方は、1円硬貨を必ず含まない

ことも言えます。もし最適な払い方に1円硬貨がある場合には、それを1枚減らして金額  X-1 にしたときに貪欲な払い方がどう変化するか考えます。1円硬貨が含まれている場合は単にそれが1枚減り、そうでない場合はより大きい硬貨を崩した上で1円硬貨が1枚減るので合計枚数が増えます。どちらにせよ金額  X-1 は必ず条件を満たすことになるので、 X が最小値であることに反します。

これまでの内容を整理します。条件を満たす金額  X の最適な払い方と貪欲な払い方それぞれが含むコインについて、以下の必要条件が成り立ちます。

最適な払い方 貪欲な払い方
1円硬貨 含まない -
 A 円硬貨 含む 含まない
 B 円硬貨 含まない 含む

けっこう絞れました。

答えの候補となる金額を絞る

前表から、金額  X の必要条件も分かってきます。最適な払い方では  A 円硬貨だけを使うことから  X A の倍数であり、貪欲な払い方に  A 円硬貨が含まれないことから  X B で割った余りは  A 未満であることが分かります。そして  B 以上である必要があります。

この条件を満たす数が実際どのようになるのか、具体例で考えます。例えば  A = 3, B = 10 としましょう。上記の条件を満たす数は、以下の図のようになります。

f:id:betrue12:20190803181058p:plain

これはつまり、正である  B の倍数それぞれに対して、右側にある最も近い  A の倍数です。これは正である  B の倍数を  A で割った「切り上げ」に  A を掛け直したもの、つまり  k=1, 2, 3, ... に対する  x_{k} = \lceil\frac{kB}{A}\rceil A として列挙することができます。

これでも候補はまだ無限個ありますが、実は

  • もし  x_{1} が条件を満たさないのであれば、全ての  x_{k} は条件を満たさない

ということが言えます。公式解説ではこの証明は略されていたので、書いておきましょう。

証明

数学的帰納法のように「 x_{1} x_{k} が条件を満たさないことを仮定すると、  x_{k+1} も条件を満たさない」ことを示すことで証明します。

金額  x_{k} = \lceil\frac{kB}{A}\rceil A について  r_{k} = x_{k} \% B と置きます。先ほど書いたように  x_{k} B で割った余りが  A 未満になるように決めているので  r_{k} \lt A が成り立ちます。

このとき  x_{k} に対して、「 A 円硬貨だけで払う」払い方Pと「大きい方から貪欲に払う」払い方Qを考えます。払い方Pは  A 円硬貨  \lceil\frac{kB}{A}\rceil 枚になり、払い方Qは  B 円硬貨  k 枚と1円硬貨  r_{k} 枚になります。いま金額  x_{k} が条件を満たさないという仮定を置いているので、 \lceil\frac{kB}{A}\rceil \ge k + r_{k} が成り立っていると仮定します。

ここから金額を  x_{k+1} に変更したときの変化を考えます。このとき  x_{k} と比べて増える金額は、 x_{1} もしくはそれより  A 円だけ少ない数になります。先ほどの  A = 3, B = 10 の例で言うと  x_{1} の値は12で、  x_{k+1} - x_{k} の値は9, 9, 12, 9, 9, 12, ... という値になります。 A 少なくなる時というのは、具体的には  r_{k} + r_{1} \ge A である時です。

この2パターンについて、2通りの払い方がどのように変わるか考えます。

  • もし  x_{k+1} - x_{k} = x_{1} であれば、 x_{k+1} の払い方は  x_{k} x_{1} の払い方をP, Qそれぞれそのまま合わせたものになります。
  • もし  x_{k+1} - x_{k} = x_{1} - A であれば、 x_{k+1} の払い方は  x_{k} x_{1} の払い方をP, Qそれぞれ合わせたものに対して、払い方Pについて  A 円を1枚、払い方Qについて1円硬貨を  A 枚取り除いたものになります。

これはどちらも、 x_{k} x_{1} の払い方を足したもの、あるいはその上で貪欲な払い方Qの枚数をより多く減らしたものになっています。よって  x_{k} x_{1} が条件を満たさないという仮定のもとでは、 x_{k+1} も条件を満たしません。

これで  x_{1} が条件を満たさない場合は解がないことが示されたので、この値1つだけを試すことで答えを求めることができます。

ACコード

Aizu Online Judge Arena