Problem D

Day 3 Problem D
Greedy, Greedy.
ACM/ICPC
Japanese Alumni Group
講評担当: 吉野
問題概要

コインのセットが与えられるので、以下の
2 点を検査せよ
 任意の金額(正の整数)が支払えるか

さもなくば、”Cannot pay some amount” と出力
 貪欲法はつねに最適の支払い方を与えるか


さもなくば、”Cannot use greedy algorithm” と出力
コインは高々 50 枚、価値は 1000 未満
問題基本情報

中嶋によるオリジナル問題

前提知識
1
次元 DP によるコインの最適支払い
サブミット状況

Total 29 submits
5
accepts

Hige, echizen.com, λ, Falcon, clax (時間順)
 First

acceptance: 34min.
2 番目は 1 時間後
echizen.com, clax はほとんど一発
 λ, Falcon はハマっていたみたいです
 kitsune-, Makegumi はもっとハマって(ｒｙ
 Hige,
サブミット状況
解法

最小のコインが 1 でなければ、支払えない
金額がある (Cannot pay some amount)
{7, 77, 777} ⇒ 10 を払えない
 逆に 1 ならば任意の整数を支払える
 Ex.

あとは実際に「ある範囲」まで最適な支払い
方と貪欲法による枚数を比べればよい
 最適解は
DP で求まる (おそらく頻出？)
 どの範囲まで調べればよいかは後述
最適な支払い方を求めるには

1 次元 DP (動的計画法) を行う

M(x)
0
1
0
1
…
x – ci
7
…
x – c1
5
x
… 6
min をとる
 金額
x、コインの枚数を n として O(nx) 時間
貪欲法による支払い

…は説明しなくてもわかりますよね
unsigned count = 0, rem = amount;
for(int i = coins.size() – 1; i >= 0; i--)
count += rem / coins[i], rem %= coins[i];
どこで打ち切ればよい？

コインの列 {ci}i=1..m (単調増加)について
「貪欲法が失敗する最小の金額 x は
を満たす」
 証明は
Kozen, Zaks. Optimal Bounds for the
Change-Making Problem. 1994. を参照
⇒ 最後の 2 枚の和(< 最大のコインの2 倍)
まで調べればよい
ということで

想定解法は「2 倍までチェックする」
 一応定数倍までは

OK というつもりでした
n×1,000×50 でだいたい 104～105 のオーダー
 自乗してしまったチームは、データが甘かった
ためうっかり通ってしまったものと思ってください

|Д`) .oO( OK になるデータは作るの大変なんだよー )
散見された間違い

隣り合ったコインが倍数・約数の関係 ⇔ OK
は成り立つと思いますが、逆は必ずしも成り
立ちません
⇒

Ex. ドル紙幣は {1, 2, 5, 10, 20, 50, 100} ですが、OK
です
 おそらく日本円のコインからの類推？
まとめ

論証部分さえできてしまえば簡単な問題です
 おそらくこの日の問題セット中では一番簡単な
部類に入る
 解けなかったチームは何故解けなかったかをよく
反省して、本番に活かしてください
TLE, WA の山を生成してしまったところも改善すべき
ところがあるかと思います
 ていうか東京.*大学勢どうした!?

サブミット状況 (再掲)

Download Report