ABC169のD問題について【Java】
今回もAtCoderの記事です。
昨日の解けなかったD問題の復習をしました。
昨日のABC169の結果はこちらです。
developer-bpeldi2oerkd8.hatenablog.com
コンテスト中に出した答え
コンテスト中に出した答えはこちらです。
エラトステネスの篩を応用して解こうとしましたが、素数判定に使う配列の個数がintを超えてしまったため、うまくいきませんでした。(WAです)
import java.util.Arrays; import java.util.Scanner; public class Main { //java11 public static void main(String[] args) { Scanner sc = new Scanner(System.in); long N = sc.nextLong(); int sqrt = (int)Math.sqrt(N); boolean[] isPrime = isPrimeN(sqrt); long ans = 0; for(int i=2; i<=sqrt; i++) { long n = N; if(isPrime[i]) { for(long j=i; j<=N; j*=i) { if(n >= 2 && n % j == 0) { ans++; n /= j; }else break; } } } if(ans == 0 && N >= 2) ans++; System.out.println(ans); } //n以下のすべての数の高速な素数判定(エラトステネスの篩) public static boolean[] isPrimeN(int n) { boolean[] isPrime = new boolean[n+1]; Arrays.fill(isPrime, true); isPrime[0] = false; isPrime[1] = false; //割れる数はsqrt以下 for(int i=2; i<=Math.sqrt(n); i++) { if(isPrime[i]) { for(int j=i*i; j<=n; j+=i) { isPrime[j] = false; } } } return isPrime; } }
修正した結果
Twitterを見てると解法らしきものが1文ほどで書いてあったので、それをもとに自力で修正してみました。
解法としては素因数分解を使い、同じ数のうちは1個たまったらカウントし、次は2個たまったらカウントし・・・という風にカウントするまでにたまる上限の数を1ずつ増やしていきました。
自作の素因数分解用のライブラリでは、最小の約数を返すようになってるので、例えば24の場合は
2, 2, 2, 3
と値を返すので、2が1個たまったら答えを+1、次は2が2個たまったら答えを+1、約数の値が変わったらまた3が1個たまったら答えを+1とし、これを繰り返すことで最後に答えの値を返します。
プログラムは次のような感じです。(もうちょっときれいに書けた気もする)
import java.util.Scanner; public class Main { //java11 public static void main(String[] args) { Scanner sc = new Scanner(System.in); long N = sc.nextLong(); int ans = 0; long n = N; long before_yakusuu; long yakusuu = -1; long count = 0; //指数 long limit = 0; //現在の必要上限(1, 2, 3, ...と増やしていく) while(n >= 2) { before_yakusuu = yakusuu; yakusuu = fact(n); if(yakusuu == -1) { break; } if(yakusuu != before_yakusuu) { count = 1; limit = 0; }else { count++; } if(count > limit) { ans++; limit++; count = 0; } n /= yakusuu; } System.out.println(ans); } //最小の約数を返す(素因数分解用) public static long fact(long n){ if(n < 2) return -1; for(long i=2; i<=Math.sqrt(n); i++) { if(n % i == 0) return i; } return n; } }
というわけで、ABC169のD問題の復習でした。
コンテスト中には、素因数分解を使ったアプローチでは何となくTLEになるのではと思っていましたが、間違いでした。
今回は完全に間違ったアプローチで解いてしまったので、そこから時間内に修正できるように練習を重ねていきたいです。