#1169218 (Java) No.3 ビットすごろく

• 問題: No.3 ビットすごろく
• ユーザー: shin
• 提出日時: 2026-06-17 15:54:34
• 言語: Java (openjdk 25.0.2)
• 結果: AC
• 実行時間: 97 ms / 5,000 ms
• コード長: 890 bytes
• コンパイル時間: 5,459 ms
• コンパイル使用メモリ: 85,460 KB
• 実行使用メモリ: 46,604 KB
• 最終ジャッジ日時: 2026-06-17 15:54:45
• 合計ジャッジ時間: 9,137 ms
• ジャッジサーバーID （参考情報）: judge3_0 / judge1_0

ファイルパターン	結果
other	AC * 33

ソースコード

import java.util.ArrayDeque;
import java.util.Scanner;

public class No3 {

	public static void main(String[] args) {
		Scanner scanner = new Scanner(System.in);
		
		int N = Integer.parseInt(scanner.next());
		
		scanner.close();
		
		int[] mass = new int[N+1];
		
		mass[1] = 1;
		int i = 1,bit = 0;
		
		ArrayDeque<Integer> arrayDeque = new ArrayDeque<>();
		arrayDeque.add(1);
		
		while(!arrayDeque.isEmpty()) {
			i= arrayDeque.pop();
			
			bit = Integer.bitCount(i);
			
			if(mass[i] == 0) {
				continue;
			}
			
			if(mass[i-bit] > mass[i]+ 1 || mass[i-bit]== 0 ) {
				mass[i-bit] = mass[i] + 1;
				arrayDeque.add(i-bit);
			}
			
			if(i+bit > N) {
				continue;
			}else if(mass[i+bit] > mass[i] + 1 || mass[i+bit] == 0) {
				mass[i+bit]= mass[i] + 1;
				arrayDeque.add(i+bit);
			}
		}
		
		if(mass[N] == 0) {
			mass[N] = -1;
		}
		
		System.out.println(mass[N]);
	}

}