結果

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

ソースコード

diff #
raw source code 

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>();
		return searchRoute(1, goal, routes);
	}

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

		if (location == goal) {
			return afterRoutes.size();
		}

		int binaryTotal = calcurateBinaryTotal(location);

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

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

		return -1;
	}

	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