#485891 (Java21) No.3 ビットすごろく

• 問題: No.3 ビットすごろく
• ユーザー: maruyuki95
• 提出日時: 2020-05-22 23:39:32
• 言語: Java21 (openjdk 21)
• 結果: AC
• 実行時間: 149 ms / 5,000 ms
• コード長: 1,803 bytes
• コンパイル時間: 1,743 ms
• コンパイル使用メモリ: 74,372 KB
• 実行使用メモリ: 60,012 KB
• 最終ジャッジ日時: 2023-09-14 01:44:35
• 合計ジャッジ時間: 7,118 ms
• ジャッジサーバーID （参考情報）: judge13 / judge12

入力	結果	実行時間; 実行使用メモリ
testcase_00	AC	111 ms; 56,352 KB
testcase_01	AC	112 ms; 56,172 KB
testcase_02	AC	112 ms; 55,708 KB
testcase_03	AC	149 ms; 55,804 KB
testcase_04	AC	118 ms; 55,952 KB
testcase_05	AC	145 ms; 56,208 KB
testcase_06	AC	121 ms; 56,156 KB
testcase_07	AC	119 ms; 55,812 KB
testcase_08	AC	113 ms; 56,736 KB
testcase_09	AC	148 ms; 56,184 KB
testcase_10	AC	145 ms; 58,436 KB
testcase_11	AC	145 ms; 55,796 KB
testcase_12	AC	137 ms; 56,188 KB
testcase_13	AC	110 ms; 56,192 KB
testcase_14	AC	137 ms; 60,012 KB
testcase_15	AC	141 ms; 58,924 KB
testcase_16	AC	129 ms; 58,536 KB
testcase_17	AC	139 ms; 58,356 KB
testcase_18	AC	120 ms; 55,956 KB
testcase_19	AC	138 ms; 58,336 KB
testcase_20	AC	108 ms; 56,080 KB
testcase_21	AC	103 ms; 55,908 KB
testcase_22	AC	138 ms; 58,524 KB
testcase_23	AC	134 ms; 58,540 KB
testcase_24	AC	139 ms; 58,452 KB
testcase_25	AC	139 ms; 58,628 KB
testcase_26	AC	103 ms; 55,696 KB
testcase_27	AC	110 ms; 56,012 KB
testcase_28	AC	140 ms; 58,228 KB
testcase_29	AC	133 ms; 56,472 KB
testcase_30	AC	103 ms; 55,984 KB
testcase_31	AC	112 ms; 55,772 KB
testcase_32	AC	134 ms; 55,924 KB

ソースコード

import java.util.HashSet;
import java.util.Scanner;
import java.util.Set;

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) {
		Set<Integer> locations = new HashSet<Integer>();
		locations.add(1);
		return search(goal, locations, locations, 1);
	}

	private int search(int goal, Set<Integer> passedLocations, Set<Integer> diffLocations, int times) {
		if (diffLocations.contains(goal)) {
			return times;
		}

		Set<Integer> newLocations = new HashSet<Integer>();
		for (Integer location : diffLocations) {
			int binaryTotal = calcurateBinaryTotal(location);

			int locationForward = location + binaryTotal;
			if (isMovedToNewLocation(goal, passedLocations, locationForward)) {
				newLocations.add(locationForward);
			}

			int locationBackward = location - binaryTotal;
			if (isMovedToNewLocation(goal, passedLocations, locationBackward)) {
				newLocations.add(locationBackward);
			}
		}

		if (newLocations.size() > 0) {
			passedLocations.addAll(newLocations);
			return search(goal, passedLocations, newLocations, ++times);
		}

		return -1;
	}

	private boolean isMovedToNewLocation(int goal, Set<Integer> passedLocations, int location) {
		return 1 <= location && location <= goal && !passedLocations.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;
	}

}