ABC099 C問題: とりあえずDPは良くない?
教育的な内容だったのでメモ.
詳細は上記リンクより参照.
問題の概要:
1<=N<=100000 Nは整数
であるときにN円を支払いたいとする. 一回に支払える金額は
1円 6円, 6^2円, 6^3円, ... 9円, 9^2円, 9^3円, ...
のいずれかである.
この制約下で合計N円を支払う時に少なくとも必要な支払いの数を求める.
何も考えずに以下の考え方でDPを適用してもO(NlogN)だけど...
合計N円を支払う際に必要な支払いの回数をf(N)とすると f(N) = min(f(N-1), f(N-6), f(N-6^2), f(N-6^3), ... , f(N-9), f(N-9^2), f(N-9^3), ... )
#include <algorithm>
#include <bitset>
#include <cassert>
#include <cctype>
#include <chrono>
#include <climits>
#include <cmath>
#include <complex>
#include <cstdio>
#include <cstring>
#include <deque>
#include <fstream>
#include <functional>
#include <iomanip>
#include <iostream>
#include <iterator>
#include <list>
#include <map>
#include <numeric>
#include <queue>
#include <random>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <utility>
#include <valarray>
#include <unordered_map>
#include <unordered_set>
#include <vector>
// namespace
using namespace std;
// type
using ll = long long;
using ull = unsigned long long;
using ld = long double;
using PAIR = pair<int, int>;
using PAIRLL = pair<ll, ll>;
// input
#define INIT ({ ios::sync_with_stdio(false); cin.tie(0); })
#define VAR(type, ...) type __VA_ARGS__; var_scan(__VA_ARGS__);
template<typename T>
static void var_scan(T& t)
{
cin >> t;
}
template<typename T, typename... R>
static void var_scan(T& t, R&... rest)
{
cin >> t;
var_scan(rest...);
}
// output
#define OUT(var) cout << (var)
#define SPC cout << ' '
#define TAB cout << '\t'
#define BR cout << '\n'
#define ENDL cout << endl
#define FLUSH cout << flush
// debug
#ifdef DEBUG
#define EPRINTF(fmt, ...) fprintf(stderr, fmt, __VA_ARGS__)
#define DUMP(var) cerr << #var << '\t' << (var) << '\n'
#define DUMPITERABLE(i) do { \
cerr << #i << '\t'; \
for (const auto& it : i) { cerr << it << ' '; } \
cerr << '\n'; \
} while (0)
#define DUMPITERABLE2(i2) do { \
cerr << #i2 << '\t'; \
for (const auto& it : i2) { \
for (const auto& it2: it) { \
cerr << it2 << ' '; \
} \
} \
cerr << '\n'; \
} while (0)
#else
#define EPRINTF(fmt, ...)
#define DUMP(var)
#define DUMPITERABLE(i)
#define DUMPITERABLE2(i)
#endif
// util
// [l, r)
#define REP(i, n) for (int i = 0; i < (n); i++)
#define RREP(i, n) for (int i = (n)-1; i >= 0; i--)
#define FOR(i, l, r) for (int i = (l); i < (r); i++)
#define RFOR(i, r, l) for (int i = (r)-1; i >= (l); i--)
#define REPLL(i, n) for (ll i = 0; i < (n); i++)
#define RREPLL(i, n) for (ll i = (n)-1; i >= 0; i--)
#define FORLL(i, l, r) for (ll i = (l); i < (r); i++)
#define RFORLL(i, r, l) for (ll i = (r)-1; i >= (l); i--)
static ll dparr[100000+1] = {0};
static PAIRLL get_maxe(ll n)
{
ll maxe_6 = 0;
ll maxe_9 = 0;
while (true) {
if (n < pow(6, maxe_6)) {
maxe_6--;
break;
} else {
maxe_6++;
}
}
while (true)
if (n < pow(9, maxe_9)) {
maxe_9--;
break;
} else {
maxe_9++;
}
return make_pair(maxe_6, maxe_9);
}
static ll dp(ll n)
{
PAIRLL maxe = get_maxe(n);
ll sub;
vector<ll> minvec;
FORLL(i, 1, maxe.second+1) {
sub = pow(9,i);
if (n-sub == 0)
goto zero;
if (!dparr[n-sub])
dparr[n-sub] = dp(n-sub);
minvec.push_back(dparr[n-sub]);
}
FORLL(i, 1, maxe.first+1) {
sub = pow(6,i);
if (n-sub == 0)
goto zero;
if (!dparr[n-sub])
dparr[n-sub] = dp(n-sub);
minvec.push_back(dparr[n-sub]);
}
if (n-1 == 0)
goto zero;
if (!dparr[n-1])
dparr[n-1] = dp(n-1);
minvec.push_back(dparr[n-1]);
return (*min_element(minvec.begin(), minvec.end()))+1;
zero:
return 1;
}
int main(void)
{
INIT;
VAR(ll, n);
OUT(dp(n));
ENDL;
return 0;
}
しかし, 一回の支払いの単位が1円 (e.g. 60 or 90), 6n円, 9n円に限られていることに注目すると, 以下の考え方でも解ける.
3通りに場合分け 1. 6^0円 or 6^n円のみで支払う場合→Nを6進数に変換し, 各桁の数字の合計を取る 2. 9^0円 or 9^n円のみで支払う場合→Nを9進数に変換し, 各桁の数字の合計を取る 3. 1円, 6^n円, 9^n円を使い支払う場合→Nを6の累乗円で支払う部分, 9の累乗円で支払う部分に分けて全探索 各々の値のうち最小値が答え.
面白い...
