結果
問題 | No.308 素数は通れません |
ユーザー |
|
提出日時 | 2016-09-28 15:35:56 |
言語 | Java (openjdk 23) |
結果 |
AC
|
実行時間 | 140 ms / 1,000 ms |
コード長 | 5,249 bytes |
コンパイル時間 | 4,051 ms |
コンパイル使用メモリ | 80,736 KB |
実行使用メモリ | 55,972 KB |
最終ジャッジ日時 | 2024-11-27 18:47:41 |
合計ジャッジ時間 | 20,230 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 107 |
ソースコード
package puzzle.yukicoder.primeimpassable;import java.math.BigInteger;import java.util.ArrayList;import java.util.Arrays;import java.util.List;import java.util.Scanner;public class PrimeImpassable {private static List<Integer> primeList;public static void main(String[] args) {Scanner cin = new Scanner(System.in);BigInteger n = new BigInteger(cin.next());cin.close();int w;/** wが1のとき、スタートである1に隣接するのは素数である2のみなので、どこへも移動できない。* wが2以上で、w+1が素数のとき、スタートである1に隣接する2とw+1へ移動できないため、どこへも移動できない。* なので、w+1が素数でない数字のみをwの候補として検討する。* w=3のとき、4へ移動できる。しかし5と7へ移動できないので、N=4のときのみw=3が答え。* w=5のとき、6へ移動できる。しかし7と11へ移動できないので、N=6のときのみw=5が答え。* w=7のとき、8,9,10,15,16,22が移動可能な範囲全てである。Nが上記の場合にw=7となる。* w=8のとき、9,10,18,26,27,28,20,21,22,14,15,16と移動することで全ての列に移動することができる。wが偶数の場合、偶数列目は全ての数字が偶数なので、上下に好きなだけ移動することができる。* Nが偶数であれば、必ず到達することができる。またNが奇数でも一番左の列(N mod 8 = 1)でなければ、左隣の偶数から移動してくれば良い。またN-8が素数でなければ、そのマスには偶数であるN-7から左に移動することができるので、そこから下に移動してNに到達可能。* 全ての列に到達するまでに通る最大のマスは28であり、28に到達するまでに26,27を通過しているので、N>=26において、N mod 8 = 1かつN-8が素数、以外の数はw=8が答え。* 同様にw+1が素数ではない偶数のwを探すと、次の候補は14である。w=14のとき、全ての列に到達するために通過する一番大きいマスは46である。46へは44,45を通過するので、N>=44であれば、 N mod 14 = 1 かつ N-14が素数 でなければw=14で成り立つ。* 以上より、N<26の時と、N<46でw=8が成り立たない数字の場合のみ、全探索を実行する。それ以外のケースはw=8もしくはw=14が解。*//* 全探索は44未満の場合しかやらないので、そこまでの素数を列挙しておく。 */primeList = Arrays.asList(2, 3, 5, 7, 11, 13, 17, 19, 23, 27, 29, 31, 37, 41, 43);if (n.compareTo(new BigInteger("26")) < 0) {/* 26までの数字は、w=8で全ての偶数列に到達できないケースなので全探索する */w = checkAllRoot(n.intValue());} else if (n.compareTo(new BigInteger("44")) < 0 && n.mod(new BigInteger("8")).equals(new BigInteger("1")) && n.subtract(new BigInteger("8")).isProbablePrime(8)) {/* 44までの数字は、w=14で全ての偶数列に到達できないケースなので全探索する */w = checkAllRoot(n.intValue());} else if (n.mod(new BigInteger("8")).equals(new BigInteger("1")) && n.subtract(new BigInteger("8")).isProbablePrime(8)) {w = 14;} else {w = 8;}System.out.println(w);}private static int checkAllRoot(int n) {for (int w = 1; w < n; w++) {if (primeList.contains(w + 1)) {continue;}if (w == n - 1) {return w;}List<Integer> reachedBlock = new ArrayList<Integer>();List<Integer> currentBlock = new ArrayList<Integer>();reachedBlock.add(1);currentBlock.add(1);while (!currentBlock.isEmpty()) {List<Integer> nextBlock = new ArrayList<Integer>();for (int block : currentBlock) {if ((block - 1) % w > 0 && !primeList.contains(block - 1) && !reachedBlock.contains(block - 1)) {nextBlock.add(block - 1);}if (block + 1 <= n && (block - 1) % w < w - 1 && !primeList.contains(block + 1) && !reachedBlock.contains(block + 1)) {nextBlock.add(block + 1);}if ((block - 1) / w > 0 && !primeList.contains(block - w) && !reachedBlock.contains(block - w)) {nextBlock.add(block + w);}if (block + w <= n && (block - 1) / w < n / w && !primeList.contains(block + w) && !reachedBlock.contains(block + w)) {nextBlock.add(block + w);}}if (nextBlock.contains(n)) {return w;}reachedBlock.addAll(nextBlock);currentBlock = nextBlock;}}return -1;}}