bpeldi2oerkd8の開発日誌

とあるひよっこエンジニアの成長の記録。

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になるのではと思っていましたが、間違いでした。
今回は完全に間違ったアプローチで解いてしまったので、そこから時間内に修正できるように練習を重ねていきたいです。