Codeforces Round #315 Div1 A: Primes or Palindromes?

解法

2000000以下の素数と回文を全列挙して、全てのnについて条件を満たすかどうかしゃくとり法で調べれば良い。

コード

import java.util.ArrayList;
import java.util.BitSet;
import java.util.Collections;
import java.util.Scanner;

public class Main {
	public void solve() {
		Scanner scanner = new Scanner(System.in);
		int p = scanner.nextInt();
		int q = scanner.nextInt();
		scanner.close();

		int Range = 2000000;
		int[] primes = sieveEratos(Range);
		Integer[] pal = getPalindromes(Range);
		int max = 0;

		int priNum = 0;
		int palNum = 0;
		for (int n = 1; n < Range; n++) {
			if (priNum < primes.length && primes[priNum] == n) {
				priNum++;
			}
			if (palNum < pal.length && pal[palNum] == n) {
				palNum++;
			}

			if (priNum * q <= palNum * p) {
				max = n;
			}
		}
		System.out.println(max);

	}

	// Eratosthenesの篩
	private int[] sieveEratos(int n) {
		BitSet primeset = new BitSet();
		primeset.flip(2, n + 1);
		for (int q = primeset.nextSetBit(2); q != -1 && q * q <= n; q = primeset
				.nextSetBit(q + 1)) {
			for (int i = q * q; i <= n; i += q) {
				primeset.clear(i);
			}
		}

		int[] primes = new int[primeset.cardinality()];
		int p = 0;
		for (int q = primeset.nextSetBit(2); q != -1; q = primeset
				.nextSetBit(q + 1)) {
			primes[p++] = q;
		}
		return primes;
	}

	private Integer[] getPalindromes(int n) {
		ArrayList<ArrayList<Integer>> list = new ArrayList<>();
		int N = String.valueOf(n).length() + 1;
		for (int i = 0; i < N; i++) {
			list.add(new ArrayList<Integer>());
		}
		for (int digit = 0; digit < N; digit++) {
			if (digit == 0) {
				for (int i = 0; i < 10; i++) {
					list.get(digit).add(i);
				}
			} else if (digit == 1) {
				for (int i = 0; i < 10; i++) {
					list.get(digit).add(i * 11);
				}
			} else {
				for (int i = 0; i < 10; i++) {
					for (Integer j : list.get(digit - 2)) {
						int next = (int) (i * Math.pow(10, digit) + j * 10 + i);
						list.get(digit).add(next);
					}
				}
				Collections.sort(list.get(digit));
			}
		}
		ArrayList<Integer> ret = new ArrayList<>();
		for (int i = 0; i < N; i++) {
			for (Integer j : list.get(i)) {
				if (j == 0) {
					continue;
				}
				char[] check = String.valueOf(j).toCharArray();
				for (int k = 0; k < check.length; k++) {
					if (check[k] != check[check.length - 1 - k]) {
						break;
					}
					if (k == check.length - 1) {
						ret.add(j);
					}
				}
			}
		}
		Collections.sort(ret);
		return ret.toArray(new Integer[0]);

	}

	public static void main(String[] args) {
		new Main().solve();
	}

}