結果

問題 No.3 ビットすごろく
ユーザー ShotaroSuzu
提出日時 2020-05-23 23:34:18
言語 Java11
(openjdk 11.0.6)
結果
TLE   .
実行時間 -
コード長 4,481 Byte
コンパイル時間 4,267 ms
使用メモリ 89,424 KB
最終ジャッジ日時 2020-05-23 23:34:31

テストケース

テストケース表示
入力 結果 実行時間
使用メモリ
testcase_00 AC 125 ms
25,928 KB
testcase_01 AC 131 ms
24,884 KB
testcase_02 AC 130 ms
24,892 KB
testcase_03 AC 137 ms
24,860 KB
testcase_04 TLE -
testcase_05 -- -
testcase_06 -- -
testcase_07 -- -
testcase_08 -- -
testcase_09 -- -
testcase_10 -- -
testcase_11 -- -
testcase_12 -- -
testcase_13 -- -
testcase_14 -- -
testcase_15 -- -
testcase_16 -- -
testcase_17 -- -
testcase_18 -- -
testcase_19 -- -
testcase_20 -- -
testcase_21 -- -
testcase_22 -- -
testcase_23 -- -
testcase_24 -- -
testcase_25 -- -
testcase_26 -- -
testcase_27 -- -
testcase_28 -- -
testcase_29 -- -
testcase_30 -- -
testcase_31 -- -
権限があれば一括ダウンロードができます

ソースコード

diff #
package yukicoder.level2.bitsugoroku;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.Scanner;

public class BitSugorokuAmend {

	private static final int START_POINT = 1;
	private int goalNumber;
	
	public static void main(String[] args) {
		new BitSugorokuAmend().execute();
	}

	private void execute() {
		// やること
		//1.入力する数字の一つ前になりうる点をあげる
		//2.そのうち、実際に来れるやつを列挙し、[自分,列挙1][自分,列挙2]という経路を作る
		//4.「列挙が一つもない場合は、「列挙」は到達不能なので自分自身を含む配列を消す
		//5.列挙に自身が属する配列に一度でも出てきた数があれば自分自身を含む配列を消す(無限ループにならないように)
		//3.この操作を列挙1,列挙2について「列挙」が1になるまで繰り返す
		//6.1までたどり着いたもののうち、最も個数が少ないものの経路数を数える
		
		goalNumber = read();
		List<Integer> initialRoute = Arrays.asList(goalNumber);
		List<List<Integer>> routes = new ArrayList<>();
		routes.add(initialRoute);
		
		
		List<List<Integer>> fullRoutes = new ArrayList<>();
		traceRoutesRecursively(routes, fullRoutes);
		
		output(getShortestRouteSize(fullRoutes));
	}

	private void output(int size) {
		System.out.println(size);
	}

	private int getShortestRouteSize(List<List<Integer>> routes) {
		int shortestRouteSize = Integer.MAX_VALUE;
		for (List<Integer> route : routes) {
			if(shortestRouteSize > route.size()) {
				shortestRouteSize = route.size();
			}
		}
		
		if(shortestRouteSize == Integer.MAX_VALUE) {
			return -1;
		}
		return shortestRouteSize;
	}

	private void traceRoutesRecursively(List<List<Integer>> routes, List<List<Integer>> fullRoutes) {
		for (List<Integer> route : routes) {
			Integer lastNum = route.get(route.size() - 1);
			List<Integer> probablePrevNumbers = getProbalbePrevNumbers(lastNum);
			
			if(isStartPoint(probablePrevNumbers)) {
				route.add(probablePrevNumbers.get(0));
				fullRoutes.add(route);
				continue;
			}
			
			List<List<Integer>> newRoutes = new ArrayList<>();
			for (Integer probableNumber : probablePrevNumbers) {
				if(route.contains(probableNumber)) {
					continue;
				}
				
				List <Integer> newRoute = new ArrayList<Integer>(route);
				newRoute.add(probableNumber);
				newRoutes.add(newRoute);
			}
			traceRoutesRecursively(newRoutes, fullRoutes);
		}
	}

	private boolean isStartPoint(List<Integer> probableNumbers) {
		return probableNumbers.isEmpty() == false && probableNumbers.size() == 1 && probableNumbers.get(0) == START_POINT; 
	}

	private List<Integer> getProbalbePrevNumbers(int distNum) {
		int probableRange = calcProbableRange(distNum);
		
		List<Integer> probableNumbers = new ArrayList<>();
		
		probableNumbers.addAll(getBackwordProbableNumbers(distNum, probableRange));
		probableNumbers.addAll(getForwardProbableNumbers(distNum, probableRange));
		
		return probableNumbers;
	}
	
	private List<Integer> getBackwordProbableNumbers(int distNum, int range) {
		List<Integer> backwordProbableNumbers = new ArrayList<>();
		for(int candidate = (distNum - range) ; candidate < distNum; candidate++) {
			int forwardNumber = calcForwardOrBackwardNumber(candidate);
			if(candidate + forwardNumber == distNum) {
				backwordProbableNumbers.add(Integer.valueOf(candidate));
			}
		}
		return backwordProbableNumbers;
	}
	
	private List<Integer> getForwardProbableNumbers(int distNum, int range) {
		List<Integer> forwardProbableNumbers = new ArrayList<>();
		for(int candidate = distNum + 1 ; candidate <= distNum + range; candidate++) {
			if(candidate > goalNumber) {
				continue;
			}
			int forwardNumber = calcForwardOrBackwardNumber(candidate);
			if(candidate - forwardNumber == distNum) {
				forwardProbableNumbers.add(Integer.valueOf(candidate));
			}
		}
		return forwardProbableNumbers;
	}
	
	private int calcForwardOrBackwardNumber(Integer num) {
		char[] numOfBynary = Integer.toBinaryString(num).toCharArray();
		
		Arrays.sort(numOfBynary);
		String numOfBynaryString = new String(numOfBynary);
		
		return numOfBynary.length - (numOfBynaryString.indexOf("1"));
	}

	private int calcProbableRange(Integer num) {
		return Integer.toBinaryString(num).length() - 1;
	}
	private int read() {
		@SuppressWarnings("resource")
		Scanner sc = new Scanner(System.in);
		return sc.nextInt();
	}



}
0