HUPC 2019 Day1 D: 貪欲が最適？
0 likes96 views
2019/7/14 北海道大学プログラミング合宿 Day1 (北大セット) D 問題 ※文字が見えない場合は、ダウンロードするかフルスクリーンにしてご覧ください
More Related Content
More from HCPC: 北海道大学競技プログラミングサークル (20)
Recently uploaded (11)
HUPC 2019 Day1 D: 貪欲が最適？
- 2. 問題概要 ? 1 円?, A 円?, B 円?硬貨がある. ? ?額の?きい硬貨から貪欲に?払う?法だと, 使?する枚数 が最?にならないような?額の最?値を答えよ 1 < ? ≤ 10&, ? < ? ≤ 10) ??例 4 6 出?例 8
- 3. 考察 次の?つのことに気づくと解けます 1. 貪欲な?払い?と, 枚数を最?化する払い? の両?で同じ種類の硬貨が使われることはな い 2. 枚数を最?化する?払い?は A 円?のみを使 う
- 4. 考察 ? 1. の証明 X を貪欲が最適ではない?額の最?値とし, ある硬貨 T が貪欲な?払い?と枚数を最?化する払 ?の両?で使われていたとする. この時 X - T 円について考えると, 貪欲な?払い?では X 円を?払うより 1 枚少ない硬貨で X - T 円を?払う ことができる. 枚数を最?化する?払い?でも同じこ とが?える. 従って X - T 円も貪欲が最適ではなくなるが, これは X がそのような?額の最?値であることに反する.
- 5. 考察 ? 2. の気持ち 1. からそれぞれの硬貨は貪欲な?払い?と, 枚数最? の?払い?の両?で使われることはない 雑に?積もると 23 = 8 通り考えられるが, ??が貪欲 な?払い?であることに気をつけると?通りに絞る ことができる.
- 6. 解法 ? 1. より, その最?値を貪欲な?法で?払うのにA 円?は使わ ない → ?額を X とすると X%B < A ? 2. より, 貪欲が最適にならない?額は A の倍数 ? ?×?円より?きい?額が答えになることはない ? これらのことから +×, - ×? (1 ≤ ? ≤ ?)で表せる?額のみ を調べれば良い（実は k = 1 のみ調べれば良いです） ? 従って O(A) で解くことができます (O(1) で解くこともできます)
- 7. Writer 解 / 統計 ? Writer 解 ? TAB (C++ 20 ?) ? Tsuta_j (C++ 30 ?) ? 統計 ? AC 率 (75/209) ? FA ? On-line polyomino (17:43) ? On-site hupc_asakorooooll (25:19)