結果

問題 No.3 ビットすごろく
コンテスト
ユーザー maruyuki95
提出日時 2020-05-22 22:47:27
言語 Java
(openjdk 23)
結果
TLE  
実行時間 -
コード長 1,730 bytes
コンパイル時間 2,048 ms
コンパイル使用メモリ 77,712 KB
実行使用メモリ 73,268 KB
最終ジャッジ日時 2024-10-05 19:25:01
合計ジャッジ時間 8,861 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 3 TLE * 1 -- * 29
権限があれば一括ダウンロードができます

ソースコード

diff # 

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

public class Main {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int arg = sc.nextInt();
		int ret = new Main().execute(arg);
		System.out.println(ret);
	}

	private int execute(int goal) {
		List<Integer> routes = new ArrayList<Integer>();
		searchRoute(1, goal, routes);
		if (moveMin == null) {
			return -1;
		}
		return moveMin.intValue();
	}

	private Integer moveMin = null;
	private void searchRoute(int location, int goal, List<Integer> routes) {
		List<Integer> afterRoutes = new ArrayList<Integer>(routes);
 		afterRoutes.add(location);

		if (location == goal) {
			if (moveMin == null || afterRoutes.size() < moveMin.intValue()) {
				moveMin = afterRoutes.size();
			}
			return ;
		}

		int binaryTotal = calcurateBinaryTotal(location);

		int locationForward = location + binaryTotal;
		if (canMove(goal, afterRoutes, locationForward)) {
			searchRoute(locationForward, goal, afterRoutes);
		}

		int locationBackward = location - binaryTotal;
		if (canMove(goal, afterRoutes, locationBackward)){
			searchRoute(locationBackward, goal, afterRoutes);
		}
	}

	private boolean canMove(int goal, List<Integer> routes, int location) {
		return 1 <= location && location <= goal && !routes.contains(location);
	}


	/**
	 * 10進数の数値を2進数で表現した時の1のビット数を返す
	 * @param decimalNumber	10進数
	 * @return	2進数で表現した時の1のビット数
	 */
	private int calcurateBinaryTotal(int decimalNumber) {
		int ret = 0;
		int quotient = decimalNumber;
		do {
			ret += quotient % 2;
			quotient = quotient / 2;
		} while (quotient > 0);

		return ret;
	}

}
0