Yukicoder No.158 奇妙なお使い

,

http://yukicoder.me/problems/no/158

整礎な感じにしたくてpriority_queueした結果TLEを生やしていたが、無理矢理やれば通った。

solution

DP。財布の状態からお使い回数への関数$\mathrm{dp} : 11 \times 101 \times 10001 \to \mathbb{N}$。

DP自体は可能であるが依存関係が綺麗でなく、単なる$3$重loopを回すのでは求まらない。 これは以下のようにして回避できる。

  • 変化がなくなるまで$3$重loopを繰り返し実行する
  • $\mathrm{dp} : \mathbb{N} \times 11 \times 101 \to 10001$とする
  • メモ化再帰にする

implementation

変化がなくなるまで回した。最悪計算量が怪しそう。

#include <iostream>
#include <vector>
#define repeat(i,n) for (int i = 0; (i) < (n); ++(i))
#define repeat_reverse(i,n) for (int i = (n)-1; (i) >= 0; --(i))
using namespace std;
template <class T> bool setmax(T & a, T const & b) { if (a < b) { a = b; return true; } else return false; }
template <typename T, typename X> auto vectors(T a, X x) { return vector<T>(x, a); }
template <typename T, typename X, typename Y, typename... Zs> auto vectors(T a, X x, Y y, Zs... zs) { auto cont = vectors(a, y, zs...); return vector<decltype(cont)>(x, cont); }
const int N = 10000, N0 = 1000, N1 = 100, N2 = 1;
int main() {
    int a0, a1, a2; cin >> a0 >> a1 >> a2;
    int db;         cin >> db;
    int b0, b1, b2; cin >> b0 >> b1 >> b2;
    int dc;         cin >> dc;
    int c0, c1, c2; cin >> c0 >> c1 >> c2;
    vector<vector<vector<int> > > dp = vectors(-1, N/N0+1, N/N1+1, N/N2+1);
    repeat (i,N/N0+1) repeat (j,N/N1+1) repeat (k,N/N2+1) dp[i][j][k] = -1;
    dp[a0][a1][a2] = 0;
    int ans = -1;
    while (true) {
        bool modified = false;
        repeat_reverse (i,N/N0+1) repeat_reverse (j,N/N1+1) repeat_reverse (k,N/N2+1) if (dp[i][j][k] != -1) {
            setmax(ans, dp[i][j][k]);
            auto foo = [&](int de, int e0, int e1, int e2) {
                int di = min(i, de / N0); de -= N0 * di;
                int dj = min(j, de / N1); de -= N1 * dj;
                int dk = min(k, de / N2); de -= N2 * dk;
                if (de == 0) {
                    if (setmax(dp[i-di+e0][j-dj+e1][k-dk+e2], dp[i][j][k] + 1)) {
                        modified = true;
                    }
                }
            };
            foo(db, b0, b1, b2);
            foo(dc, c0, c1, c2);
        }
        if (not modified) break;
    }
    cout << ans << endl;
    return 0;
}