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

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

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

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

Q&A

解決済

8回答

2968閲覧

このコードの処理をどうにかして速くしたいです

snowman

総合スコア25

Java

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

0グッド

0クリップ

投稿2017/03/30 17:59

AtCoderの終了済みの問題を解いていました。
が、以下のコードではタイムアウトでうまくいきませんでした・・・
自分でも色々試してみたのですがうまくいかず・・・
どうすれば処理が軽くなりますか?

整数 N が与えられます。

ここで、2 つの正の整数 A,B に対して、F(A,B) を「10 進表記における、A の桁数と B の桁数のうち大きい方」と定義します。
例えば、F(3,11) の値は、3 は 1 桁、11 は 2 桁であるため、F(3,11)=2 となります。
2 つの正の整数の組 (A,B) が N=A×B を満たすように動くとき、F(A,B) の最小値を求めてください。

import java.util.*; public class DigitsinMultiplication { public static void main(String[] args) { // TODO Auto-generated method stub Scanner s=new Scanner(System.in); long N=s.nextLong(); int F=0; String a,b; int i=0; int min=100; for(i=1;i*i<=N;i++){ if(N%i!=0)continue; else{ a=String.valueOf(i); b=String.valueOf(N/i); if(a.length()<=b.length())F=b.length(); if(a.length()>b.length())F=a.length(); if(min>F)min=F; } } System.out.print(min); } }

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

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

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

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

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

guest

回答8

0

ベストアンサー

ABC075C問題であってますでしょうか。
とりあえず(Rubyで)解けたのでどうといていくのかを解説します。

  1. N = A×B(A ≦ B)

として√N(Nの平方根)を考えます。
A ≦ Bより両辺にNをかけて
2. A×N ≦ B×N
N = A×Bだから
3. A×A×B ≦ B×N
4. A^2×B ≦ N×B ※ ^2は2乗を表す
Bは0ではない正の整数なので両辺をNで割って
5. A^2 ≦ N
両辺の正の平方根を求めて
6. A ≦ √N ※ √は平方根を表す。
Bもどうように、
7. B ≧ √N
となることがわかります。

全てのF(A, B)の組合せはA ≦ Bの時は上の規則に従います。またF(A, B) = F(B, A)ですので、実際に確認するのはA ≦ Bの時だけです。このなからF(A, B)が最小になるものを探せば良いとなります。

次はA同士の大きさを考えます。

  1. N = Ai×Bi = Aj×Bj(Ai < Aj)

としたとき、Ai < Ajより両辺にBjをかけて
2. Ai×Bj < Aj×Bj = N = Ai×Bi
つまり、
3. Ai×Bj < Ai×Bi
Aiは正の整数なのでAiを両辺で割って
4. Bj < Bi
ここでF(A, B)AよりBの方が大きいのでBによってのみ決まります。また、大きい数字の方が桁数は大きくなりますので、
5. F(Aj, Bj) ≦ F(Ai, Bi)
が成り立ちます。

F(A, B)の組は最小を求めるのですから、あるAjF(Aj, Bj)があるなら、Ajより小さいAiのときのF(Ai, Bi)の桁がそれより小さくなることはありません。以上のことからN = A×B(A ≦ B)の組合せでAが最大の物を求めれば良いとなります。

最初に戻ってA ≦ √Nでした。つまり、√Nから順番に1ずつ減らしながら該当する最大のAを求めればいいと言うことです。該当するかどうかはNAで割った時の余りが0になるかどうかでわかります。Aが求まればN÷ABが求まるので、その桁数を数えるだけとなります。

Rubyでの解答例(AC)

最悪計算量はO(√n)です。


【補足】
√Nから増やしていく場合は最悪がN-√N回になり、計算量がO(n)のままなので、言語によっては間に合いません(少なくともRubyはTLEだった)。Nが素数の場合だけ別にするというのも2000000014(2×1000000007)とかがあるので、間に合わないと思われます。

投稿2017/03/31 10:41

編集2017/03/31 10:50
raccy

総合スコア21733

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

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

0

この状況で、どうなるとF(A,B)が最小になるか考えましょう。
N=A×Bを満たしながら動くことを考えると、例えばN=8100の時、1×8100のように一方に偏るより、90×90のように均等に分かれたほうが小さくなります。そしてこの均等な状態から少しずれようものなら、一方が3桁になっていまい、最小ではなくなります。
つまり、AとBはなるべく均等であるべきという結論になります。なので1という端の値は最終候補になります。

これをもとに、「Nの素因数を均等に分ける」と考えて組んでみたのが次のコード(未検証)。

java

1public class Q70846 { 2 3 public static void main(String[] args) { 4 try (Scanner sc = new Scanner(System.in)) { 5 System.out.println(minF(sc.nextInt())); 6 } 7 } 8 9 public static int minF(int n) { 10 int balance = 1; // 素因数を均等に分けた際の片方 11 int restMulti = 1; // ペアにならず残った素因数の積 12 List<Integer> prime = new ArrayList<>(); 13 for (int i = 2; i * i <= n; i++) { 14 boolean rest = false; // その素因数がペアにならず残っているか 15 while (n % i == 0) { 16 n /= i; 17 if (rest) balance *= i; // 素因数のペア成立時、均等に分ける 18 rest = !rest; 19 } 20 if (rest) { 21 prime.add(i); 22 restMulti *= i; 23 } 24 } 25 if (n != 1) { 26 prime.add(n); 27 restMulti *= n; 28 } 29 30 // 余った素因数がなかった場合、nは平方数ということになり、 31 // 均等に分けたbalanceが平方根となり最小の桁数 32 if(prime.isEmpty()) { 33 return (int)Math.log10(balance) + 1; 34 } 35 36 // 素因数をなるべく均等になるように分配する分け方を探す 37 // 重複がないよう、primeの0番が入る組と入らない組に分ける 38 int minB = Integer.MAX_VALUE; // N = A*B(A≦B)となる最小のB 39 for (int i = 2; i <= (1 << (prime.size() - 1)); i += 2) { 40 BitSet set = BitSet.valueOf(new long[]{i}); 41 int a = 1; 42 for (int j = set.nextSetBit(0); j >= 0; j = set.nextSetBit(j + 1)) { 43 a *= prime.get(j); 44 } 45 int b = restMulti / a; 46 minB = Math.min(minB, Math.max(a, b)); 47 } 48 return (int)Math.log10(minB) + 1; 49 } 50 51} 52

この方法のメリットとしては、raccyさんが出した2000000014(2×1000000007)のような極端な例の場合でも、素因数分解の仕組み上、√2000000014≒44721から目的の数2までたどるループ数よりも、素因数分解が完了するループ数√1000000007≒31623のほうがループ回数が少なくなります。(このケースで後半の素因数の組み合わせのチェックは1回しか起きないので、結果的にこちらのほうが少なくはなるが微差か)

デメリットとしては、素因数分解で孤立した素因数が多くなると、組み合わせチェックが多くなってしまうというのは考えられます。

投稿2017/03/30 21:57

編集2017/04/01 14:13
swordone

総合スコア20649

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

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

Zuishin

2017/03/31 00:46

お言葉ですが、端の値は検討する必要があると思います。例えば素数の場合、端の値が商になります。 質問者さんのアルゴリズムの問題は、同じ商を二回計算しているところと、ループ終了まで最小値が確定しないところだと思うので、「端の値は最後に検討する」という意味でおっしゃっているのなら、その通りだと思いますが、少し誤解を招く表現かと。
swordone

2017/03/31 14:49

ご指摘ありがとうございます。修正しました。 解法として素因数分解が上手く使えないかと考えましたが、かえって面倒になりそう…。
guest

0

p.rb

ruby

1require 'prime' 2 3def f_func(a, b) 4 bigger = (a > b) ? a : b 5 Math.log10(bigger).to_i + 1 6end 7 8# num の約数を list で得る 9# See http://qiita.com/seinosuke/items/fde2e0471dcf937e5a09 10def divs(num) 11 return [1] if num == 1 12 13 Prime.prime_division(num).map do |e| 14 Array.new(e[1] + 1).map.with_index do |element, i| 15 e[0] ** i 16 end 17 end.inject { |p, q| p.product(q) }.map do |a| 18 [a].flatten.inject(&:*) 19 end.sort 20end 21 22# num の約数すべての組の[a, b] の f_func(a, b) の値を求める 23def all_fs(num) 24 ans = {} 25 divs(num).each do |a| 26 b = num / a 27 f = f_func(a, b) 28 ans[f] = [] if ans[f].nil? 29 ans[f] << [a, b] 30 end 31 ans 32end 33 34def solve(num) 35 ans = all_fs(num) 36 min_f = ans.keys.sort.first 37 p min_f 38 p ans[min_f] 39end 40 41[10000, 1000003, 9876543210, 2000000014].each { |num| solve(num) } 42

実行例

$ time ruby p.rb 3 [[16, 625], [20, 500], [25, 400], [40, 250], [50, 200], [80, 125], [100, 100], [125, 80], [200, 50], [250, 40], [400, 25], [500, 20], [625, 16]] 7 [[1, 1000003], [1000003, 1]] 6 [[13005, 759442], [26010, 379721], [379721, 26010], [759442, 13005]] 10 [[1, 2000000014], [2, 1000000007], [1000000007, 2], [2000000014, 1]] real 0m0.187s user 0m0.085s sys 0m0.048s

num の約数の組 [a, b] をすべて求め、それぞれに対して f(a, b) を求めていきます。 (f(a,b)を key, [a, b] を value にした hash に保存します)
求まった hash の key の最小値を画面に出力します。
num = 10000, 1000003, 9876543210, 2000000014 に対して処理をしてみています。 私の環境 (MacBook Pro, ruby 2.4.1) では 全体で 0.2 秒程度で処理できています。

投稿2017/04/01 00:28

katoy

総合スコア22324

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

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

raccy

2017/04/01 01:27

Rubyのprime_divisionは試し割っぽいのでO(√n)になるかと。問題は約数の個数で、調べてもよくわからなかったのですが、計算量的には無視できるのではないかと思っています。ポラード・ロー素因数分解法などさらに計算量を減らす方法があるらしいので、速度を求めるにはこちらの方が浪漫を感じますね。(問題にある10の10乗程度では違いは出ないと思いますけど)
guest

0

以下のようにすれば軽くなると思いますが、正しい結果となっているかどうかは定かではありません

java

1import java.util.*; 2 3public class Din { 4 5 public static void main(String[] args) { 6 // TODO Auto-generated method stub 7 Scanner s=new Scanner(System.in); 8 long N=s.nextLong(); 9 int F=0; 10 String a,b; 11 int i=0; 12 int t=0; 13 String len=String.valueOf(N); 14 long k=1; 15 16 int y=0; 17 if(((len.length()/2)-1)<0){ 18 y=0; 19 }else{ 20 y=(len.length()/2)-1; 21 } 22 23 for(int p=0;p<y;p++){ 24 k*=10; 25 } 26 27 for(i=(int)k;i<=N;i++){ 28 if(N%i!=0)continue; 29 else{ 30 a=String.valueOf(i); 31 b=String.valueOf(N/i); 32 if(a.length()<=b.length()){ 33 t=b.length(); 34 } 35 if(a.length()>b.length()){ 36 t=a.length(); 37 break; 38 39 } 40 } 41 } 42 43 System.out.print(t); 44 45 } 46 47} 48

投稿2017/03/31 01:06

退会済みユーザー

退会済みユーザー

総合スコア0

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

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

Zuishin

2017/03/31 16:27

tetratail さんのインデントはいつもひどいことになっていますが、これは自分では読みやすいのですか?
guest

0

N=A×B ですから、A,Bのうち小さい方をAとしたとき、A≦√N、B≧√N が成り立ちます。(かつ、A≧1、B≦N)
問題はF(A,B)、すなわちA,Bのうちで大きい方の数値の桁数ですから、上の式からB(≧√N)の桁数が分かればよいことになります。
F(A,B)のうちの最小ということは、Bがもっとも小さい数値のときの桁数ですから、√N以上でNを割り切ることのできる最小数が求まればよいということになります。

よって、

  1. N の平方根を求める。平方根が整数である場合(すなわち、N が A^2 となっている)は、そこで候補確定
  2. 平方根が整数ではない場合、それより大きい最小の整数から順に、N を割り切れるかどうか調べる。割り切れればそこで候補確定
  3. 候補確定後、その候補の数値の桁数を計算する。(常用対数log10を計算すると出る)

ですかね。
あとは N が素数である場合、計算する必要がない(A=1, B=N であるから)ので、Nが素数かどうか先に判定する手もありますか。N がよほど巨大な数でない限り、素数判定のひと手間の方が遅くなりそうですが。

投稿2017/03/31 00:58

tacsheaven

総合スコア13703

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

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

0

ほぼ答えが出揃っていますが、まずNの平方根を求めて、その値から最も近い整数から組み合わせを探すと良いかもしれませんね。

できるだけ両者の値が大きい値同士、つまり一方の桁数が大きくなりすぎないよう求めた値を使ったほうが良いのですから、2乗すればNになる値X、つまり平方根から探すのが賢明そうです。

N=100であれば、平方根は10です。F(A,B)も2でよいですよね。
N=1000であれば平方根は33ぐらいになりますが整数ではなさそうですね。その値から近い整数から探すようにすると少しでも早くなりそうです。

投稿2017/03/30 23:12

編集2017/03/30 23:45
akabee

総合スコア1947

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

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

fuzzball

2017/03/30 23:42

「ルート2」ではなく「平方根」ですよね。
akabee

2017/03/30 23:44

そのとおりですね、修正いたしました。
guest

0

総当たりだと遅くなります。
例えば N = 100 のとき、答えは 2 だとすぐ分かりますよね?
なぜなら、1 桁の数字同士をかけ算しても 100 にはならないからです。

投稿2017/03/30 18:17

Zuishin

総合スコア28656

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

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

0

みなさまありがとうございます!
正直、自分ではまだどの方法が一番いいのかなどは分からなかったので、他の方の高評価が一番多かった方を選ばせていただきました!

投稿2017/04/01 16:05

snowman

総合スコア25

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

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

あなたの回答

tips

太字

斜体

打ち消し線

見出し

引用テキストの挿入

コードの挿入

リンクの挿入

リストの挿入

番号リストの挿入

表の挿入

水平線の挿入

プレビュー

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

ただいまの回答率
85.50%

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

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

質問する

関連した質問