質問をすることでしか得られない、回答やアドバイスがある。

15分調べてもわからないことは、質問しよう!

新規登録して質問してみよう
ただいま回答率
85.35%
Java

Javaは、1995年にサン・マイクロシステムズが開発したプログラミング言語です。表記法はC言語に似ていますが、既存のプログラミング言語の短所を踏まえていちから設計されており、最初からオブジェクト指向性を備えてデザインされています。セキュリティ面が強力であることや、ネットワーク環境での利用に向いていることが特徴です。Javaで作られたソフトウェアは基本的にいかなるプラットフォームでも作動します。

アルゴリズム

アルゴリズムとは、定められた目的を達成するために、プログラムの理論的な動作を定義するものです。

コードレビュー

コードレビューは、ソフトウェア開発の一工程で、 ソースコードの検査を行い、開発工程で見過ごされた誤りを検出する事で、 ソフトウェア品質を高めるためのものです。

Q&A

解決済

3回答

1112閲覧

最少試行回数の見つけ方

grape_ll

総合スコア83

Java

Javaは、1995年にサン・マイクロシステムズが開発したプログラミング言語です。表記法はC言語に似ていますが、既存のプログラミング言語の短所を踏まえていちから設計されており、最初からオブジェクト指向性を備えてデザインされています。セキュリティ面が強力であることや、ネットワーク環境での利用に向いていることが特徴です。Javaで作られたソフトウェアは基本的にいかなるプラットフォームでも作動します。

アルゴリズム

アルゴリズムとは、定められた目的を達成するために、プログラムの理論的な動作を定義するものです。

コードレビュー

コードレビューは、ソフトウェア開発の一工程で、 ソースコードの検査を行い、開発工程で見過ごされた誤りを検出する事で、 ソフトウェア品質を高めるためのものです。

0グッド

0クリップ

投稿2020/05/17 06:24

問題

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

質問内容

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

Java

1for(int i = 0; i <= n; i++) { 2 int j = n - i; 3 int s = i; 4 int t = j; 5 int p = 0; 6 while(s > 0) { 7 p += (s % 6); 8 s /= 6; 9 } 10 while(t > 0) { 11 p += (t % 9); 12 t /= 9; 13 }

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

ACがでていたコード

Java

1import java.util.*; 2 3public class Main { 4 public static void main(String[] args) { 5 Scanner sc = new Scanner(System.in); 6 int n = sc.nextInt(); 7 int ans = n; 8 for(int i = 0; i <= n; i++) { 9 int j = n - i; 10 int s = i; 11 int t = j; 12 int p = 0; 13 while(s > 0) { 14 p += (s % 6); 15 s /= 6; 16 } 17 while(t > 0) { 18 p += (t % 9); 19 t /= 9; 20 } 21 ans = Math.min(ans, p); 22 } 23 System.out.println(ans); 24 } 25}

自分でかいたコード

Java

1import java.util.Scanner; 2public class StrangeBank { 3 public static void main(String[] args){ 4 Scanner scan=new Scanner(System.in); 5 int[] dp=new int[100000]; 6 dp[0]=scan.nextInt(); 7 int i=0; 8 while(true){ 9 int p=1; 10 int q=1; 11 while(p*6<dp[i]){ 12 p*=6; 13 } 14 while(q*9<dp[i]){ 15 q*=9; 16 } 17 if(dp[i]>=9){ 18 dp[i+1]=Math.min(dp[i]-p,dp[i]-q); 19 } 20 else if(dp[i]>=6){ 21 dp[i+1]=dp[i]-6; 22 } 23 else{ 24 dp[i+1]=dp[i]-1; 25 } 26 27 if(dp[i+1]==0) break; 28 i++; 29 } 30 System.out.println(i+1); 31 32 } 33}

気になる質問をクリップする

クリップした質問は、後からいつでもMYページで確認できます。

またクリップした質問に回答があった際、通知やメールを受け取ることができます。

バッドをするには、ログインかつ

こちらの条件を満たす必要があります。

YT0014

2020/05/17 09:05 編集

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

回答3

0

解説見ずに私が考案した考え方を載せておきます。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くらいの処理時間です。

java

1import java.util.*; 2 3public class Main { 4 static Map<Integer,Integer> dp = new HashMap<>(); 5 static List<Integer> depos = new ArrayList<>(); 6 7 static void doDepo(int n){ 8 List<Integer> ans = new ArrayList(); 9 for(int v : depos){ 10 if(n == v){ 11 dp.put(n,1); 12 return; 13 }else if(n > v){ 14 ans.add(dp.get(n-v) + 1); 15 } 16 } 17 int result = ans.stream().min((a, b) -> a.compareTo(b)).get(); 18 dp.put(n,result); 19 } 20 21 public static void main(String args[]) { 22 23 // 引出可能金額準備 24 depos.add(1); 25 int d = 6; 26 while(d <= 100000){ 27 depos.add(d); 28 d = d * 6; 29 } 30 d = 9; 31 while(d <= 100000){ 32 depos.add(d); 33 d = d * 9; 34 } 35 // dp準備 36 for(int i = 1; i <= 100000; i++){ 37 doDepo(i); 38 } 39 // 回答 40 System.out.println(dp.get(44852)); 41 } 42}

投稿2020/05/17 08:52

編集2020/05/17 08:58
hope_mucci

総合スコア4447

バッドをするには、ログインかつ

こちらの条件を満たす必要があります。

grape_ll

2020/05/18 12:07

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

2020/05/18 12:48

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

2020/05/19 10:34

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

0

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

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

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

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

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

投稿2020/05/17 07:33

編集2020/05/17 07:35
YT0014

総合スコア1750

バッドをするには、ログインかつ

こちらの条件を満たす必要があります。

grape_ll

2020/05/17 07:56

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

2020/05/17 08:14

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

2020/05/17 08:24

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

0

ベストアンサー

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

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

投稿2020/05/17 07:19

swordone

総合スコア20669

バッドをするには、ログインかつ

こちらの条件を満たす必要があります。

grape_ll

2020/05/17 08:08 編集

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

2020/05/17 08:12

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

2020/05/17 08:22

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

2020/05/17 08:44

逆の方が簡単でしょう。 例えば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

2020/05/20 12:14 編集

教えていただいた考えをもとに,このようにしたら無事すべてのパターンで通りました。ありがとうございました。 ###訂正したコード ```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]); } } ```
guest

あなたの回答

tips

太字

斜体

打ち消し線

見出し

引用テキストの挿入

コードの挿入

リンクの挿入

リストの挿入

番号リストの挿入

表の挿入

水平線の挿入

プレビュー

15分調べてもわからないことは
teratailで質問しよう!

ただいまの回答率
85.35%

質問をまとめることで
思考を整理して素早く解決

テンプレート機能で
簡単に質問をまとめる

質問する

関連した質問