AtCoder Biginner Contest 099 C Strange Bank

なかなかおもしろい問題が出たので、主な考察の流れを書いておこうかなと思います

問題

https://abc099.contest.atcoder.jp/tasks/abc099_c

ある銀行では、お金の引き出しを難しくするために、一回の操作で引き出せる金額が以下のいずれかとなっています。

1 円

6 円、6^2(=36) 円、6^3(=216) 円、…

9 円、9^2(=81) 円、9^3(=729) 円、…

この銀行からちょうど N 円を引き出すには少なくとも何回の操作が必要か求めてください。

ただし、一度引き出したお金を再び預け入れてはならないとします。

1 <= N <= 100000

考察

自分が意識していることの一つに、

「一気に二つのことをしようとするな」

なので、これも

「一気に6ⁿと9ⁿを扱おうとするな」

と考えて解きました(状態をうまく縮約できるときもありますが、難しい場合が多い(それはAGC))

それぞれで考えます

6ⁿだけ使える場合

このときは N を6進数で表示したときの桁の総和が答えです

9ⁿだけ使える場合

このときは N を9進数で表示したときの桁の総和が答えです

これを踏まえると....

6進数で扱う分と9進数で扱う分で分けてそれぞれの総和を足せばイケそう...?

となるのでそれをします

O(NlogN)で解くことができましたね

https://abc099.contest.atcoder.jp/submissions/2649449

クソコード

#include <bits/stdc++.h>
using namespace std;
using i64 = long long;
#define rep(i,s,e) for(int (i) = (s);(i) <= (e);(i)++)

int N;

int main(){
  cin >> N;
  int result = N;
  for(int n = 0;n <= N;n++){
    int nn = n;
    int m = N - n;

    int ans = 0;
    int nine = 1;
    while(nine * 9 <= nn) nine *= 9;
    while(nine != 1){
      ans += nn / nine;
      nn %= nine;
      nine /= 9;
    }
    ans += nn;
    nn = m;
    nine = 1;
    while(nine * 6 <= nn) nine *= 6;
    while(nine != 1){
      ans += nn / nine;
      nn %= nine;
      nine /= 6;
    }
    ans += nn;
    result = min(ans , result);
  }

  cout << result << endl;
}

もちろんDPでも解けますね...