https://atcoder.jp/contests/abc257/tasks/abc257_e
前提知識
解説
https://atcoder.jp/contests/abc257/submissions/32754197
この問題は貪欲法で解く。
アドホックな解法ではあるが、方針としてはテクとしてよく見られる方法の1つ。
何が一番大切か
答えを最大化したいと考えたときに何が優先されるだろうかを考えてみる。
数字は何よりもまず桁数が大きい方が大きい数になるので、なるべく桁数は多くなる方がいい。
桁数を多くなるには支払うお金が最も少ない数だけを使って構築するのがいい。
なので、答えの桁数については比較的簡単に求めることができる。
支払いの最小金額minCを求めておくと、答えの桁数はN/minCの切り捨てで求めることができる。
これよりも桁数を増やせないことは自明だし、これよりも桁数が小さい数を使っても答えの最大化は
達成できないので、とりあえずこれはこれでよさそう。
なぜ答えの桁数を先に求めるのか、みたいな疑問はありそうだが、
元々似たような状況の問題を解いたことがあるからテクニック的に方針を導いたというのもあるし、
色々な解法を考えた中で答えにたどり着いた1つのパス上にあったというのもある。
（こういうアドホック貪欲は色んな可能性を探っていくことになります）
頭から貪欲に整合性が保たれるように決めていく
桁数が最大化されたら、より大きい数を構築するには上の桁ほど大きい数が採用できればいい。
7???よりも9???の方が???がなんであれ大きいので上の桁の数を最大化するのが最優先である。
この部分は上の桁から順番に大きい数を使ったときに残りの桁数を残りのお金で構築できるかを判断して埋めていく。
大きい数を順番に入れていくことを考えるが、その数を採用してしまうと残りの桁が埋められないという
状況になっていれば使用することはできない。
だが、逆に使用することができるならば、絶対に使用した方が数は他の選択よりも大きくなる。
このように「頭から貪欲に整合性が保たれるように決めていく」という方針は構築問題で見られるテクの1つ。
（見方によってはこの問題も構築問題ですね…）
この方針の一部にある「残りの桁数を残りのお金で構築できるか」という問題については、
桁数の最大化の時に利用した最小金額が役に立つ。
残りの桁数を残りのお金で構築する最適な方法は最小金額の数で埋めてしまうことなので、
これで埋めることができるかどうかを判定材料としよう。
int N, C[10]; void _main() { cin >> N; rep(x, 1, 10) cin >> C[x]; int min_C = inf; rep(x, 1, 10) chmin(min_C, C[x]); int max_len = N / min_C; string ans = ""; rep(len, 0, max_len) rrep(x, 9, 1) { int rest_len = max_len - len - 1; int rest_N = N - C[x]; if (0 <= rest_N && rest_len <= rest_N / min_C) { ans += char('0' + x); N -= C[x]; break; } } cout << ans << endl; }
