結果

問題 No.3 ビットすごろく
ユーザー velfare_nagatavelfare_nagata
提出日時 2016-10-05 14:12:03
言語 C#(csc)
(csc 3.9.0)
結果
AC  
実行時間 80 ms / 5,000 ms
コード長 3,786 bytes
コンパイル時間 2,240 ms
コンパイル使用メモリ 104,260 KB
実行使用メモリ 29,796 KB
最終ジャッジ日時 2023-09-14 00:09:49
合計ジャッジ時間 5,784 ms
ジャッジサーバーID
（参考情報） 		judge13 / judge12
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 59 ms
20,732 KB
testcase_01 AC 59 ms
22,688 KB
testcase_02 AC 60 ms
20,784 KB
testcase_03 AC 63 ms
21,220 KB
testcase_04 AC 61 ms
20,952 KB
testcase_05 AC 67 ms
24,120 KB
testcase_06 AC 64 ms
23,180 KB
testcase_07 AC 62 ms
23,172 KB
testcase_08 AC 67 ms
25,892 KB
testcase_09 AC 71 ms
23,072 KB
testcase_10 AC 75 ms
29,472 KB
testcase_11 AC 69 ms
25,152 KB
testcase_12 AC 68 ms
24,112 KB
testcase_13 AC 62 ms
21,336 KB
testcase_14 AC 76 ms
29,488 KB
testcase_15 AC 79 ms
29,740 KB
testcase_16 AC 78 ms
29,796 KB
testcase_17 AC 77 ms
27,792 KB
testcase_18 AC 62 ms
21,272 KB
testcase_19 AC 79 ms
27,744 KB
testcase_20 AC 60 ms
20,792 KB
testcase_21 AC 60 ms
20,656 KB
testcase_22 AC 76 ms
27,652 KB
testcase_23 AC 80 ms
29,700 KB
testcase_24 AC 80 ms
27,812 KB
testcase_25 AC 78 ms
29,792 KB
testcase_26 AC 59 ms
20,816 KB
testcase_27 AC 63 ms
23,324 KB
testcase_28 AC 79 ms
29,684 KB
testcase_29 AC 72 ms
27,156 KB
testcase_30 AC 60 ms
20,716 KB
testcase_31 AC 61 ms
20,764 KB
testcase_32 AC 70 ms
26,052 KB
権限があれば一括ダウンロードができます
コンパイルメッセージ
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;

namespace CodeIq
{
	internal class Program
	{
		/// <summary>各数値に対応するビットフラグ数のテーブル</summary>
		private static Hashtable _bitCountTable;
		/// <summary>すごろくマス数</summary>
		private static int _n;
		/// <summary>計算要素スタック</summary>
		private static Stack _stack;
		/// <summary>位置に対応する最短手順数</summary>
		private static Hashtable _history;
		/// <summary>現時点での最短手</summary>
		private static int _nowBestOrderCount;

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

			_nowBestOrderCount = int.MaxValue;
			_stack = new Stack();
			_stack.Push( 1 );
			_history = new Hashtable();
			_history.Add( 1, 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 );

			for( var i = 1; i <= _n; i++ )
				_history[i] = int.MaxValue;

			// ゴールまでの経路を計算する
			var result = Calculate( 1 );
			//Debug.Print( ( result != int.MaxValue ? result : -1 ).ToString() );
			Console.WriteLine( ( result != int.MaxValue ? result : -1 ) );
		}

		private static int Calculate( int orderCount )
		{
			// 現時点での最短手を超過している場合はそれ以上計算しても無駄
			var pos = (int)_stack.Pop();
			if( orderCount > _nowBestOrderCount )
				return int.MaxValue;

			// 前方向と後方向への移動をそれぞれ計算する
			// ※前→後ろの順でチェックする
			if( pos == _n )
				return orderCount;

			// 移動先が範囲外だったり、前回来た時よりも手数を上回っている場合は処理しない
			// この時点で手数が上回っている場合はどうやっても巻き返せない
			var calcCount = 0;
			var backward = pos - (int)_bitCountTable[pos];
			if( ( backward > 0 && (int)_history[backward] > orderCount + 1 ) )
			{
				_stack.Push( backward );
				_history[backward] = orderCount + 1;
				calcCount ++;
			}
			var forward = pos + (int)_bitCountTable[pos];
			if( forward <= _n && ( (int)_history[forward] > orderCount + 1 ) )
			{
				_stack.Push( forward );
				_history[forward] = orderCount + 1;
				calcCount++;
			}

			var result = int.MaxValue;
			for( var i = 0; i < calcCount; i++ )
			{
				var calculatedCount = Calculate( orderCount + 1 );
				if( result > calculatedCount )
					result = calculatedCount;
				if( _nowBestOrderCount > result )
					_nowBestOrderCount = result;
			}
			return result;
		}
	}
}
0