agc044_aの解き方の解説 Pay to Win 変則的な深さ優先探索(dfs)

感謝の正拳突き１万回ならぬ、競プロサイトで 1 日 1AC(正解)するように頑張る。

昨日はじめて AtCoder Grand Contest(AGC)に挑戦しましたが 1 問も解けずに撃沈。今日は振り返りながらAGC の A 問題 Pay to Win を解いていきます。

逆に答えから辿る

「0 から初めて n へするには」という問題は、最初に答えからたどるか、スタートからたどるか考えます。今回の問題はコイン d 枚を支払って 1 マイナスできるので、スタートから辿ると無限にルートができます。また支払ったコインで DP できそうですが、n が 10^18 とメモリ不足になります。

スタートから辿るのは無理筋なので、答えからたどる方向です。

DFS で間に合う

時間内にここまでは思いついたのですが、どうたどればいいか検討がつきませんでした。コイン d 枚を支払って 1 増減できるせいで、dfs だと深くなりすぎるように思ったせいで、無駄に複雑なロジックを考えてしまいました。

他の方の回答を参考にしてみたら、よく考えたらコイン d 枚を支払って 1 増減できる部分は O(1)で計算可能で再帰する必要がありませんでした。

となると 2,3,5 で割っていくので、余裕で間に合います。

dfs のロジックを考えていきましょう

初めは単純に 1 ずつ減らした場合を考える

1 ずつ減らせばいずれ 0 に到着します。

x * d

で簡単に計算できます。

倍率の倍数になるように足すか引くか 2 パターン辿る

元の問題が?倍にする問題なので、割り切れなければなりません。

割れるようにするためには、倍数になるように足すか引くかする必要があります。 どちらのほうが総コインが低くなるのかわからないため、両方とも探索してみる必要があります。

ひとまず 5 倍にするパターンだけ考えてみましょう。

引く場合

5 で割るコインは c なので、コインを c 枚払います。

割り切れるようにするには x mod 5 の分だけ引けばいいです。x mod 5 * d 枚かかります。

割った後は x / 5 の切り捨てが残るので、次の dfs に x / 5 を渡します。

トータルで c + x % 5 * d + dfs(x / 5)枚かかります。

足す場合

割り切れるようにするために必要なコインの枚数と、割った後に残る x が変わります。

割り切れるように足すには 5 - x mod 5 を足します。5 - x mod 5 * d 枚コインがかかります。

割った後は x / 5 の切り上げが残ります。(x + (5 - 1)) / 5 で切り上げ計算ができます。

トータルで c + (5 - x % 5) * d + dfs((x + (5 - 1)) / 5)枚かかります。

2,3 も同様

2,3 も同じです。

引く場合は 割るコイン枚数 + abs(x % 倍率) * d + dfs(x / 倍率)

足す場合は 割るコイン枚数 + abs(倍率 - x % 倍率) * d + dfs((x + 倍率 - 1) / 倍率)

となります。

メモ化する

dfs(x / 倍率)と dfs((x + 倍率 - 1) / 倍率)はちょうど割り切れる数字の場合同じ結果になるので、メモ化が有効です。メモ化しておかないと O(NlogN)くらいかかってしまいます。

メモ化には unorderedmap が有効です。map は内部的にキーが昇順で並んで保持しているので、参照も insert も O(logN)かかります。unorderedmap は hash で持つので、参照も insert も O(1)です。ただし hash が衝突する場合は最悪 O(n)になる可能性があります。が、競プロの場合キーに数値型を使う場合が多いので、まず衝突は考えなくて大丈夫でしょう。ただタイプ数が多く、O(logN)なので大して遅くもなく、map を好んで使う方が多いようです。

できあがり

#include <bits/stdc++.h>
using namespace std;
#define ll long long

template<class T>inline bool chmin(T &a, const T &b) {if(a>b){a = b; return 1;} return 0; };

ll n, a, b, c, d;
unordered_map<ll, ll> memo;
ll dfs(ll x){
    if(x == 0) return 0;
    if(x == 1) return d;
    if(memo.count(x)) return memo[x];

    ll result = LLONG_MAX / d > x ? x * d : LLONG_MAX;
    ll rate, pay;

    rate = 2;
    pay = a;
    // 引いて割る
    chmin(result,
        pay +
        x % rate * d +
        dfs(x / rate)
    );
    // 足して割る
    chmin(result,
        pay +
        abs(rate - x % rate) * d +
        dfs((x + rate - 1) / rate)
    );

    rate = 3;
    pay = b;
    // 引いて割る
    chmin(result,
        pay +
        x % rate * d +
        dfs(x / rate)
    );
    // 足して割る
    chmin(result,
        pay +
        abs(rate - x % rate) * d +
        dfs((x + rate - 1) / rate)
    );


    rate = 5;
    pay = c;
    // 引いて割る
    chmin(result,
        pay +
        x % rate * d +
        dfs(x / rate)
    );
    // 足して割る
    chmin(result,
        pay +
        abs(rate - x % rate) * d +
        dfs((x + rate - 1) / rate)
    );


    return memo[x] = result;
}

int main(){
    int t;
    cin >> t;
    for(int i = 0; i < t; i++) {
        memo.clear();
        cin >> n >> a >> b >> c >> d;
        cout << dfs(n) << endl;;
    }
}