結果

問題 No.3 ビットすごろく
ユーザー しめはじめしめはじめ
提出日時 2019-06-12 14:14:21
言語 PHP
(8.2.11)
結果
AC  
実行時間 11 ms / 5,000 ms
コード長 1,152 bytes
コンパイル時間 498 ms
コンパイル使用メモリ 12,056 KB
実行使用メモリ 12,268 KB
最終ジャッジ日時 2023-09-14 01:19:21
合計ジャッジ時間 2,108 ms
ジャッジサーバーID
(参考情報)
judge12 / judge14
このコードへのチャレンジ(β)

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 8 ms
12,200 KB
testcase_01 AC 7 ms
12,204 KB
testcase_02 AC 8 ms
12,172 KB
testcase_03 AC 9 ms
12,184 KB
testcase_04 AC 9 ms
12,088 KB
testcase_05 AC 9 ms
12,188 KB
testcase_06 AC 8 ms
12,204 KB
testcase_07 AC 8 ms
12,248 KB
testcase_08 AC 9 ms
12,180 KB
testcase_09 AC 9 ms
12,200 KB
testcase_10 AC 10 ms
12,200 KB
testcase_11 AC 9 ms
12,196 KB
testcase_12 AC 9 ms
12,208 KB
testcase_13 AC 8 ms
12,184 KB
testcase_14 AC 10 ms
12,216 KB
testcase_15 AC 10 ms
12,220 KB
testcase_16 AC 10 ms
12,212 KB
testcase_17 AC 10 ms
12,184 KB
testcase_18 AC 8 ms
12,088 KB
testcase_19 AC 11 ms
12,084 KB
testcase_20 AC 8 ms
12,220 KB
testcase_21 AC 8 ms
12,216 KB
testcase_22 AC 10 ms
12,156 KB
testcase_23 AC 10 ms
12,268 KB
testcase_24 AC 11 ms
12,172 KB
testcase_25 AC 10 ms
12,220 KB
testcase_26 AC 7 ms
12,212 KB
testcase_27 AC 8 ms
12,204 KB
testcase_28 AC 10 ms
12,224 KB
testcase_29 AC 9 ms
12,184 KB
testcase_30 AC 7 ms
12,200 KB
testcase_31 AC 7 ms
12,180 KB
testcase_32 AC 9 ms
12,204 KB
権限があれば一括ダウンロードができます
コンパイルメッセージ
No syntax errors detected in Main.php

ソースコード

diff #

<?php
// 移動数(1の立った個数を数える)
function GetMoveStep( $n ){
  $step = $n;
  $n = $n - (($n >> 1) & 0x55555555);
  $n = ($n & 0x33333333) + (($n >> 2) & 0x33333333);
  $n = ($n + ($n >> 4)) & 0x0f0f0f0f;
  $n = $n + ($n >> 8);
  $n = $n + ($n >> 16);
  return $n & 0x3f;
}

// 入力値
$n = trim( fgets( STDIN ) );
// キュー
$queue[] = 1;
// 回数記録用
$dist = array();
$dist[1] = 1;
for( $i = 2; $i <= 10000; $i++ ){
    $dist[$i] = -1;
}
//番兵
$banpei = 0;

while( count( $queue ) > 0 && $banpei < 10000 ){
    
    // キューの頭(現在地)を取得して除く
    $idx = $queue[0];
    array_shift( $queue );
    // 移動先を得る
    $step = GetMoveStep( $idx );
    $pos_f = $idx + $step;
    $pos_b = $idx - $step;
    // 移動先に対して加算していく、キューも貯める
	if ( $pos_f >= 1 && $pos_f <= $n && $dist[$pos_f] == -1 ) {
		$dist[$pos_f] = $dist[$idx] + 1;
		$queue[] = $pos_f;
	}
	if ( $pos_b >= 1 && $pos_b <= $n && $dist[$pos_b] == -1 ) {
		$dist[$pos_b] = $dist[$idx] + 1;
		$queue[] =  $pos_b;
	}
    //暴走防止番兵
    $banpei++;
}
printf( "%d\n", $dist[$n] );
0