結果
問題 |
No.3 ビットすごろく
|
ユーザー |
|
提出日時 | 2014-11-12 09:38:38 |
言語 | Java (openjdk 23) |
結果 |
AC
|
実行時間 | 172 ms / 5,000 ms |
コード長 | 1,148 bytes |
コンパイル時間 | 3,583 ms |
コンパイル使用メモリ | 77,848 KB |
実行使用メモリ | 54,676 KB |
最終ジャッジ日時 | 2024-07-01 07:06:34 |
合計ジャッジ時間 | 9,564 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 33 |
ソースコード
import java.util.Arrays; import java.util.PriorityQueue; import java.util.Scanner; public class BitSugoroku { public static void main(String[] args) { BitSugoroku p = new BitSugoroku(); } public BitSugoroku() { Scanner sc = new Scanner(System.in); int n = sc.nextInt(); solve(n); } public void solve(int n) { int[] isVisit = new int[n+1]; Arrays.fill(isVisit, -1); PriorityQueue<P> queue = new PriorityQueue<P>(); queue.offer(new P(1, 1)); while(!queue.isEmpty()){ P p = queue.poll(); if(isVisit[p.x] < 0) isVisit[p.x] = p.d; else continue; int move = Integer.bitCount(p.x); if(p.x+move <= n && isVisit[p.x+move] < 0){ queue.offer(new P(p.x+move, p.d+1)); } if(p.x-move >= 1 && isVisit[p.x-move] < 0){ queue.offer(new P(p.x-move, p.d+1)); } } System.out.println(isVisit[n]); } public class P implements Comparable<P>{ public int x; public int d; public P(int x, int d) { this.x = x; this.d = d; } @Override public int compareTo(P o) { return this.d - o.d; } } }