結果

問題 No.3 ビットすごろく
ユーザー velfare_nagatavelfare_nagata
提出日時 2016-10-05 11:35:55
言語 C#(csc)
(csc 3.9.0)
結果
WA  
実行時間 -
コード長 2,372 bytes
コンパイル時間 1,025 ms
コンパイル使用メモリ 115,508 KB
実行使用メモリ 27,504 KB
最終ジャッジ日時 2024-05-01 12:47:55
合計ジャッジ時間 4,520 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge1
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 24 ms
17,792 KB
testcase_01 AC 24 ms
17,664 KB
testcase_02 AC 23 ms
17,536 KB
testcase_03 AC 46 ms
18,176 KB
testcase_04 AC 24 ms
17,920 KB
testcase_05 AC 121 ms
19,328 KB
testcase_06 AC 50 ms
18,688 KB
testcase_07 AC 26 ms
18,048 KB
testcase_08 WA -
testcase_09 WA -
testcase_10 WA -
testcase_11 WA -
testcase_12 AC 116 ms
19,200 KB
testcase_13 AC 40 ms
18,688 KB
testcase_14 AC 236 ms
20,480 KB
testcase_15 AC 352 ms
20,736 KB
testcase_16 WA -
testcase_17 WA -
testcase_18 AC 26 ms
18,304 KB
testcase_19 WA -
testcase_20 WA -
testcase_21 AC 24 ms
17,792 KB
testcase_22 AC 244 ms
20,224 KB
testcase_23 AC 361 ms
20,864 KB
testcase_24 WA -
testcase_25 WA -
testcase_26 AC 24 ms
17,536 KB
testcase_27 WA -
testcase_28 WA -
testcase_29 WA -
testcase_30 WA -
testcase_31 AC 24 ms
17,536 KB
testcase_32 WA -
権限があれば一括ダウンロードができます
コンパイルメッセージ
Microsoft (R) Visual C# Compiler version 3.9.0-6.21124.20 (db94f4cc)
Copyright (C) Microsoft Corporation. All rights reserved.

ソースコード

diff # 

using System;
using System.Collections;
using System.Diagnostics;

namespace CodeIq
{
	internal class Program
	{
		/// <summary>各数値に対応するビットフラグ数のテーブル</summary>
		private static Hashtable _bitCountTable;

		/// <summary>
		/// Carol は特殊なすごろくをしようとしている。
		/// 
		/// 1からNの番号がふられている一直線に並べられているN個のマスがある。
		/// 1から開始のマスとして、ゴールはNが書かれているマスとする。
		/// 
		/// その場に書かれている数字の2進数で表現した時の1のビット数 だけ「前」または「後」に進めることができる。
		/// (1未満とN+1以上のマスには移動することは出来ない、正確にNにならないとゴールできない）
		/// 
		/// 自然数Nを与えられた時、ゴールに到達できる最短の移動数（開始のマスへも移動にカウントする）を求めてください。
		/// 到達できない場合は-1を出力してください。
		/// 
		/// 開始のマスがすでにゴールになっている場合もあリます。
		/// </summary>
		private static void Main()
		{
			var n = int.Parse( Console.ReadLine() );
			//var n = 1333;
			var moveCount = 1;
			var finished = false;
			var stack = new Stack();
			var history = new Stack();
			stack.Push( 1 );
			history.Push( 1 );

			var getBitCount = new Func<int, int>( target =>
			{
				var bitCount = 0;
				for( ; target > 0; target &= target - 1 )
					bitCount++;
				return bitCount;
			} );

			_bitCountTable = new Hashtable();
			for( var i = 1; i < n; i++ )
				_bitCountTable[i] = getBitCount( i );

			// ゴールまでの経路を計算する
			while( stack.Count > 0 )
			{
				var pos = (int)stack.Pop();
				if( pos == n )
				{
					finished = true;
					break;
				}

				moveCount++;
				var backward = pos - (int)_bitCountTable[pos];
				if( !history.Contains( backward ) && backward > 0 )
				{
					stack.Push( backward );
					history.Push( backward );
				}

				var forward = pos + (int)_bitCountTable[pos];
				if( !history.Contains( forward ) && forward <= n )
				{
					stack.Push( forward );
					history.Push( forward );
				}
			}
			Debug.Print( ( finished ? moveCount : -1 ).ToString() );
			Console.WriteLine( finished ? moveCount : -1 );
		}
	}
}
0