日記

のみろぐ

主に競プロ日記です

ABC099-C「Strange Bank」

ABC099-C「Strange Bank

考察

コンテスト中の考察

  • 価値の大きい金から使っていく貪欲で解けそう
  • 貪欲だと上手くいかない...
  • もしかしたらDPでは?→DP書けない

理想の考察

  • 本質部分はコイン問題と同じじゃん!!
  • 違う部分は使うコインの種類が与えられるのではなくて初めから決まっているという点。
  • $6^{a}, 9^{b}, 1$を使うから複雑そうに見えるけど、種類を全部列挙して「使うコインの種類」を表す配列に入れればシンプルになる。
  • すると、コイン問題と同じように解ける


コード

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

const int INF = 1e8;
int N;
vector<int> c;
int dp[111111];

int main() {
    cin >> N;

    // コインの種類を配列に追加
    c.push_back(1);
    for (int i = 6; i <= N; i*=6) { c.push_back(i); }
    for (int i = 9; i <= N; i*=9) { c.push_back(i); }

    // DPテーブルを初期化
    fill(dp, dp+N+1, INF);
    dp[0] = 0;

    // DP
    for (int i = 0; i <= N; i++) {
        for (int j = 0; j < c.size(); j++) {
            if (i >= c[j]) {
                dp[i] = min(dp[i], dp[i-c[j]]+1);
            }
        }
    }

    cout << dp[N] << endl;

    return 0;
}


要点

  • コイン問題に帰着できることに気づくことが大事だった
  • いろんな種類のコインを1つの配列で管理してシンプルにする事が大事だった


感想

  • 典型力って大事だなーと思った。
  • コイン問題知ってるだけでこの問題解けたじゃん!!