ABC099 C (DP&全探索) - ゆるふわ競プロ

DP(1次元)と全探索の複合問題

abc099.contest.atcoder.jp

この問題はこちらにも書いてある通りC問題にしては難しいです.しっかり理解したい方はこの記事読んだ方が100倍わかりやすいです。

提出コード

問題
1 , 6^p , 9^q のうちから好きな数を選び取り合計をnにする時に数字を選びとる回数の最小値を求める。

取りうる値の小さい順に並べると(1は無視します。)

6  ,  9  ,  36  ,  81  ,  216  ,  729  ,  1296  ,  6561  ,  7776  ,  59049  ,  46656

これらの数字の和に1を何回か加えて目標の数字nを作ります。この時に大きい数字から取るって考えをするとWAで弾かれます。
例えば n = 12 の時12以下の最大の数字で使えるのは9なので9を使い...とやってしまうと

12 = 9 + 1 + 1 + 1

の4回数字を使うことになってしまいます。しかし今回は間違えになってしまいます直感的に12と言われ気づいた方もいると思いますが今回は

12 = 6 + 6

こちらの計算の仕方を行うことで数字の登場回数は2回に抑えることができ最小の回数となります。
人間ならパッと気づきそうなこと(nが大きくなると無理ですが)をプログラムに任せなくてはなりません。

DPの登場

ここで今回DPを用います.DPは動的計画法(Dynamic Program)といい配列を用意してそれぞれの要素の値を次々に変更していきます.
今回の問題では 1 という数字を使っていいと言われているので確実に目的のn という数字を作ることが可能になります。

    DP[i] :  数字 i を作る時に数字を選ぶ回数の最小値

と定義します。
上の例で行くと DP[12] = 2となります。(6 と 6 の2回)今回求めたいのは DP[n]になります。nを作る時に最初の回数を出します。DP を少しでもやったことがある方はここまで行く方はいるでしょう。(ボクも曖昧にDPっぽいなと思いました) しかしこの後DPテーブル(配列)をどのように埋めていけばいいかわかりませんでした.

全探索でDPテーブルを埋める

今回の問題はnの値に制約がありそこまで大きくないので全探索でDPテーブルを埋めにかかります。

    dp[0] = 0;
    for ( int i = 1 ; i < n + 1 ; i ++){
        dp[i] = dp[i - 1] + 1;
    }

初期化してみます。実際にはdp[i] のi >= 6 の部分では 6以上の数字を使った方が効率がいいのでn まで全て初期化する必要はないはありません。とりあえず1という数字だけを何回使ったら目的の数字が出るかを出しました。DPは最初は答えの数字が入っていなくても大丈夫なのです。この後動的に配列の中身を変化させていきます。

        for (int six = 1; six <= n; six *= 6) {
            for (int j = 1; j < n + 1; j++) {
                if (j - six < 0) {
                    continue;
                }
                dp[j] = Math.min(dp[j - six] + 1, dp[j]);
            }
        }

9のn乗は考えずに6のn乗と1のみを使って最小回数のDPテーブルを作ります。今回意識すべきこととしては

    43 = 1 + 6 + 36
    43 = 1 + 36 + 6
    43 = 36 + 1 + 6
   DP[43] = 3

となるため数字のたす順番は関係ないということです。なので今回は6 を足して 36 を足して... と繰り返しています。同様のことを9のn乗でも行います.

        for (int nine = 1; nine < n + 1; nine *= 9) {
            for (int j = 1; j < n + 1; j++) {
                if (j - nine < 0) {
                    continue;
                }
                dp[j] = Math.min(dp[j - nine] + 1, dp[j]);
            }
        }

これでDPテーブルのDP[0] ~ DP[n] までが全て埋まるので DP[n]を出力して終了です。

DPには色々種類があるようですので一つ一つ学んでいきましょう。

追記

他の方の解答が面白かった

ソースコード

この解答みていて綺麗だなと思いました。

まずnを適当に二つに分けます

次に片方を6のp乗の大きい方から順に割っていきます。(216で割って,36で割って6で割るそれぞれ割った商が使った数字の回数になります)最後に6で割った際のあまりは1を加えるとみなしてカウントする.

同様に2つに分けた残りを9のp乗の大きい数字から割っていきます.

これを分ける場所を全部変えることで答えを出していく方針です。

理解してもかけないことが多いので書いてみる
書いたコード
結果はWAでした。テストケース全部とおたのでいけるかと思ったら2WAしていました.
ボクの嫌いな少しだけWAを出してしまいました.こういう時は端っこの数字や0などの特徴的な数でWAしている可能性が高い!!(はず)
残念ながら最小の数字1を通してもしっかり1と出力されてしまいました。 f:id:topaz1-3:20190222165648p:plain 本当に適当に入力していたら見つかった!!(奇跡)本当似たまたまです。
* 原因

for (int i = 1; i <= n; i++) 
for (int i = 0; i <= n; i++)

for分の繰り返しの初期値が1になっていました.このせいで2に分割する時に全てを9側に分割することができていませんでした。
他人のソースコードチラ見するの勉強にもなるし楽しいですね