結果

問題 No.3 ビットすごろく
コンテスト
ユーザー ShotaroSuzu
提出日時 2020-05-23 23:34:18
言語 Java
(openjdk 23)
結果
TLE  
実行時間 -
コード長 4,481 bytes
コンパイル時間 4,142 ms
コンパイル使用メモリ 80,412 KB
実行使用メモリ 219,332 KB
最終ジャッジ日時 2024-10-09 12:53:19
合計ジャッジ時間 11,441 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 4 TLE * 1 -- * 28
権限があれば一括ダウンロードができます

ソースコード

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.１までたどり着いたもののうち、最も個数が少ないものの経路数を数える
		
		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