最少試行回数の見つけ方

Question

問題

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

質問内容

問題は上記のリンクの通りになっていて，自分の考え的には動的計画法をもちいてやるのかなと思ったのですが，三つ目のサンプルすら通りませんでした。頭で計算してみても自分のコードの取り出し方とは違った方法のときに最小の取り出し方になるのが分かったので，解けている方のコードやヒントを見てみたのですが，どちらをみてもなぜこの計算で答えが出るのか分からなかったので，仕組みを教えていただければと思い質問させていただきました。具体的には、次の箇所が分かりません。

for(int i = 0; i <= n; i++) {
      int j = n - i;
      int s = i;
      int t = j;
      int p = 0;
      while(s > 0) {
        p += (s % 6);
        s /= 6;
      }
      while(t > 0) {
        p += (t % 9);
        t /= 9;         
      }

ACがでたコードの下に自分でかいたコードも載せさせていただきます。また、dpを用いたやり方も教えていただけると大変参考になりますので，よろしければ是非お願いします。

ACがでていたコード

import java.util.*;
 
public class Main {
  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    int n = sc.nextInt();
    int ans = n;
    for(int i = 0; i <= n; i++) {
      int j = n - i;
      int s = i;
      int t = j;
      int p = 0;
      while(s > 0) {
        p += (s % 6);
        s /= 6;
      }
      while(t > 0) {
        p += (t % 9);
        t /= 9;         
      }
      ans = Math.min(ans, p);
    }
    System.out.println(ans);
  }
}

自分でかいたコード

import java.util.Scanner;
public class StrangeBank {
    public static void main(String[] args){
        Scanner scan=new Scanner(System.in);
        int[] dp=new int[100000];
        dp[0]=scan.nextInt();
        int i=0;
        while(true){
            int p=1;
            int q=1;
            while(p*6<dp[i]){
                p*=6;
            }
            while(q*9<dp[i]){
                q*=9;
            }
            if(dp[i]>=9){
                dp[i+1]=Math.min(dp[i]-p,dp[i]-q);
            }
            else if(dp[i]>=6){
                dp[i+1]=dp[i]-6;
            }
            else{
                dp[i+1]=dp[i]-1;
            }
            
            if(dp[i+1]==0) break;
            i++;
        }
        System.out.println(i+1);
        
    }
}

Comments

[YT0014]

質問者のコードですが、残金額と出金回数をどう管理しているのか、という視点で見直してみてください。
ポイントは、p、qがいくつであっても、出金回数は1回だということです。

Answer 1

解説見ずに私が考案した考え方を載せておきます。DPを使った解法です。（例題が全て正解したのは確認済み）

n<100000で引出金額として取りうるのは次の12通りです。

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

引出回数最小を求める関数をd(n)とすると、
d(1) = 1
d(2) 以降は、1回目の引出金額をnの超えない範囲で引出パターンから選び、d(n-1回目金額)が最小になるものを回とします。
例えば、
n=2の場合は、1回目の引出金額が1、二回目以降はd(2-1) == d(1) しかないので、解は2。
n=14の場合は、1回目の引出金額が9,6,1の3パターンあるので、d(5)、d(8)、d(13)のうち最小になるものを探して+1したものが解。このうちd(8)とd(13)が3で最小なのでd(14)は4。

このようにn=1から順に計算していき、結果を逐次記録しておけばO(n)の計算量で結果が求まります。
下記のコードでだいたい300msくらいの処理時間です。

import java.util.*;

public class Main {
    static Map<Integer,Integer> dp = new HashMap<>();
    static List<Integer> depos = new ArrayList<>();

    static void doDepo(int n){
        List<Integer> ans = new ArrayList();
        for(int v : depos){
            if(n == v){
                dp.put(n,1);
                return;
            }else if(n > v){
                ans.add(dp.get(n-v) + 1);
            }
        }
        int result = ans.stream().min((a, b) -> a.compareTo(b)).get();
        dp.put(n,result);
    }
    
    public static void main(String args[]) {
        
        // 引出可能金額準備
        depos.add(1);
        int d = 6;
        while(d <= 100000){
            depos.add(d);
            d = d * 6;
        }
        d = 9;
        while(d <= 100000){
            depos.add(d);
            d = d * 9;
        }
        // dp準備
        for(int i = 1; i <= 100000; i++){
            doDepo(i);
        }
        // 回答
        System.out.println(dp.get(44852));
    }
}

Comments

[grape_ll]

最初に6と９のべき乗を取ってくる考え方があったのですね。
とても参考になりなした。ありがとうございます。

[hope_mucci]

注目してほしいポイントは、どうやって漸化式を構築したか--d(n)の一般化についてです。
d(n)とd(n-1)の関係をどうやって見出すかに慣れていけばこの手の問題は難しくないです。

[grape_ll]

そのようですね、漸化式を導く経験値を沢山積むようにしたいと思います。
助言ありがとうございます。

Answer 2

ＡＣのコードの説明だけで申し訳ないのですが。

入力された金額を、6側での出金額と9側での出金額に分けて、総当たりをしています。
変数i:6側での出金額
変数j:9側での出金額
変数s:6側での出金の残額
変数t:6側での出金の残額
変数p:出金処理回数

whileループでは、指定金額の、6,9での最小出金回数を計算。

考え方としては、n を i と j に分けて、各々6進数と9進数として、変換。
各桁の合計が、最小出金回数となるのを利用。

改善の余地があるとすれば、6,9とも3の倍数なのを考慮して、3の剰余の差を同一視して、ループを減らす辺りでしょうか。

Comments

[grape_ll]

6進数と9進数の各桁の合計になっているのは驚きました。
試しに100でやってみてこのコードがどう進んでいるのかは理解できました。
ただ、初見でこの考えが浮かぶ気がしないのですが、造詣が深い人はどのようにしてこういった考えに至りますか？後学のために教えていただけると助かります。

[YT0014]

問題をみた瞬間、6と９の階乗と１が単位なので、n進数使えそうかな？と考えました。
ただ、6と9だと、うまくいかなそうと考えた状態で、ACのコードをみて、分割してからやれば良いのか、と納得しました。
基数を10なら普通に10進数が浮かぶと思うので、10を特別に考えずにnとして考えるのに慣れると、連想しやすくなると思います。

[grape_ll]

日常生活では基数が10なのが当たり前になっているのでn進数の違和感があるのですが、そういった考えに慣れていくことが重要なのですね。ありがとうございます。

Answer 3

ACのやり方は、
0. まず引き出したい金額を2グループに分ける。
0. 片方のグループは6円ずつ分け、もう片方のグループは9円ずつ分ける。
0. 6円ごとに分けたグループを考えると、端数は1円ずつ引き落とすしかない。そのため、余りの数だけ引き出す回数がかかる。
0. 6円の組をさらに6つまとめたかたまりを作ることを考える。かたまりとなったものは6²円以上の金額として引き落とせる可能性があるが、そうならなかったもののグループ数分、6円で引き落とす必要がある。
これを繰り返していき、6^n円で引き落とす回数をカウントする。
0. 9円ずつのグループに関しても同様に考える。
0. これをすべてのグループの分け方について考え、最小となる回数を求める。

DPでやる場合は、「ある金額を引き落とすための最小引き落とし回数」を記録した配列を作ることになります。

Comments

[grape_ll]

ACの進め方は理解することが出来ました。
ありがとうございます。
ただ、自分でこのような問題にであったときにこのような考えが思い浮かぶ気がしないのですが，どのようにしたらこういった考えが出てくるようになるのか等が分かりましたら教えていただけると幸いです。

[swordone]

「方向性があっている」といいつつ、コードでは全く違うことをやっています。
これでは、「引き落とし1回ごとの残り引き落とし金額の最小」を記録しています。
金額が少なければ必要な引き出し回数が少なくなる、という前提なら成立しますが、そうはなりません。
18円なら9円2回に対し、36円なら36円1回で引き落とせる、などの反例があります。

[grape_ll]

すいません、頭のなかとやっていることが分離していたみたいです。
dpを勉強したてでまだどこをメモすればいいのか慣れていないです。申し訳ございません。
ある金額を引き落とすための最小引き落とし回数を記録するということは、ACのやっていたことを最初のほうで行っていき、残金が９の何乗とか６の何乗とかであれば1を足したりするということでしょうか

[swordone]

逆の方が簡単でしょう。
例えば9円引き落としには1回で済むので、そこから＋6円、つまり15円引き落とすのは、9円引き落としの回数1回＋6円引き落としの1回の計2回でできるということになります。
同様に、1回目を9円引き落としとすると、2回目の引き落とし方が9円、81円、729円、…と6円、36円、216円、…となるので、18円、90円、738円、…と15円、45円、225円、…の引き落とし回数が2回と(暫定的に)考えられます。
(暫定的に)と書いたのは、引き落とし方次第ではより回数の少ないパターンが見つかるかもしれないためそう書きました。
1円については、6回以上引き落としのパターンは確実に6円引き落としなどのパターンに置き換えたほうが回数が少なくなるため、最後に5回以下として調整すれば十分です。

[grape_ll]

教えていただいた考えをもとに，このようにしたら無事すべてのパターンで通りました。ありがとうございました。
###訂正したコード
```Java
import java.util.Scanner;
public class StrangeBank {
public static void main(String[] args){
Scanner scan=new Scanner(System.in);
int[] dp=new int[100001];
dp[0]=0;
int n=scan.nextInt();
int i=1;
int num=0;
int[] element=new int[100];
while(i*9<=n){
i*=9;
element[num]=i;
num++;
}
i=1;
while(i*6<=n){
i*=6;
element[num]=i;
num++;
}
int flag=0;
for(int k=1;k<=n;k++){
dp[k]=100000;
flag=0;
for(int l=0;l<num;l++){
if((k-element[l])>=0){
int box=Math.min(dp[k-1],dp[k-element[l]])+1;
dp[k]=Math.min(dp[k],box);
flag++;
}
}
if(flag==0) dp[k]=dp[k-1]+1;
}
System.out.println(dp[n]);
}
}
```