AOJ 0186 Aizu Chicken 解説

OkNCT-ICT 2013 春合宿 Day5(らしい) に解説したもの.

Transcript

1. AOJ 0186 Aizu Chicken 解説 @kagamiz
2. 問題概要 • ？？？？？？ • 問題文クソ難しいんだよね ... • 頑張って読む
3. 問題概要 • あなたには予算が b 円あります . • 会津地鶏が 1 個 c1 円 , ふつうの鶏肉が 1 個 c2 円で 買える . • ただし , 会津地鶏は q2 個までしか買えない .
4. 問題概要 • 鶏肉が足りなくなると困るので、 q1 個以上の鶏肉を買 う . • 予算の許す範囲で会津地鶏をできるだけ多く買う ( 会津 地鶏は 1 個以上買わなければならない ). • 会津地鶏を買った残りでふつうの鶏肉をできるだけ多く 買う ( 予算が足りなければ買わない ).
5. アルゴリズムの考察 • 1. まず , できるだけ会津地鶏を買う . • 2. 残ったお金で普通の鶏肉を買う . • 3. q1 個より多くなるまで , 会津地鶏を 1 個ずつ売りな がら普通の鶏肉を買う . • 4. 会津地鶏が 0 個になったら , お母さんの言う通りに 買えないので NA を出力する . そうじゃなければ個 数を出力 .
6. アルゴリズムの計算量 • “3. q1 個より多くなるまで , 会津地鶏を 1 個ずつ売り ながら普通の鶏肉を買う ." • これやばそう？ • 実はそうでもない ( 各変数 ≦ 10^6 なので , ループは 最悪でも 10^6 しか繰り返されない .)
7. 実☆装 • できるだけ " アルゴリズムの考察 " の項に素直に . – 複雑な事をするとバグります
8. 実☆装 • 1. まず , できるだけ会津地鶏を買う . • 2. 残ったお金で普通の鶏肉を買う . – aChick... 会津地鶏 bchick... 普通の鶏肉 aChick = min(b / c1, q2); b -= aChick * c1; bChick = max(0, b / c2); b -= bChick * c2;
9. 実☆装 • 3. q1 個より多くなるまで , 会津地鶏を 1 個ずつ売りな がら普通の鶏肉を買う . while (aChick + bChick < q1 && aChick){ b += c1; b += bChick * c2; bChick = b / c2; b -= bChick * c2; aChick--; }
10. 実☆装 • 4. 会津地鶏が 0 個になったら , お母さんの言う通りに 買えないので NA を出力する . そうじゃなければ個 数を出力 . if (aChick){ printf("%d %d\n", aChick, bChick); } else { printf("NA\n"); }