Factorial Yen Coin [AtCoder Beginner Contest 208 B]

https://atcoder.jp/contests/abc208/tasks/abc208_b

解説

https://atcoder.jp/contests/abc208/submissions/23993696

今回は貪欲解で解くことができる。
だが、制約を見ると動的計画法を使っても解くことができるようになっている。
ここは恐らく優しさであると思う。

貪欲？

貪欲解とは、特定のアルゴリズムではなく、特定のルールに従って、ある意味で貪欲に処理を進めていくことで
最適解を得ようとする方針である。
特定のルールといわれるとさらに分かりにくいかもしれないので、今回のルールを説明する。

今回は、「値段が高い硬貨が使えるときは使うようにして支払う」というルールに従って処理を進めていくと最適解が得られる。
実装的には、最初に10!を使うだけ使ってPを減らして答えをインクリメントしていく。
Pが10!未満になったら、次は9!を使うだけ使ってPを減らして答えをインクリメントしていく。
これを繰り返していく。

動的計画法？

これは補足であるが、DP(=動的計画法)で解ける問題が貪欲で解けるように見えてしまう場合が多々存在する。
慣れるまでは、貪欲なら解けるからとりあえずそっちでやってみるかでWAで終了というパターンに多く遭遇するかもしれない。
自分は割と、ペナルティが深刻な場合は、少し時間がかかってもDPで解けそうならそっちで解くようにしている。

int P;
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> P;

    int ans = 0;
    rrep(x, 10, 1) {
        int tot = 1;
        rep(i, 1, x + 1) tot *= i;
        while (tot <= P) {
            P -= tot;
            ans++;
        }
    }
    cout << ans << endl;
}