結果

問題 No.3 ビットすごろく
ユーザー velfare_nagatavelfare_nagata
提出日時 2016-10-05 01:55:30
言語 C#(csc)
(csc 3.9.0)
結果
MLE  
実行時間 -
コード長 3,310 bytes
コンパイル時間 4,407 ms
コンパイル使用メモリ 112,764 KB
実行使用メモリ 834,220 KB
最終ジャッジ日時 2024-11-21 17:06:56
合計ジャッジ時間 88,223 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge2
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 MLE -
testcase_01 MLE -
testcase_02 MLE -
testcase_03 MLE -
testcase_04 MLE -
testcase_05 MLE -
testcase_06 MLE -
testcase_07 MLE -
testcase_08 MLE -
testcase_09 MLE -
testcase_10 MLE -
testcase_11 MLE -
testcase_12 MLE -
testcase_13 MLE -
testcase_14 MLE -
testcase_15 MLE -
testcase_16 WA -
testcase_17 MLE -
testcase_18 AC 26 ms
26,308 KB
testcase_19 TLE -
testcase_20 WA -
testcase_21 AC 22 ms
24,688 KB
testcase_22 TLE -
testcase_23 TLE -
testcase_24 TLE -
testcase_25 TLE -
testcase_26 WA -
testcase_27 TLE -
testcase_28 TLE -
testcase_29 TLE -
testcase_30 WA -
testcase_31 AC 22 ms
26,416 KB
testcase_32 MLE -
権限があれば一括ダウンロードができます
コンパイルメッセージ
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.Collections.Generic;
using System.Diagnostics;
using System.Linq;

namespace CodeIq
{
	internal class Program
	{
		/// <summary>マス数</summary>
		private static int _n;

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

			// ゴールに到達できない場合は処理しない
			var isEnable = false;
			for( var i = 1; i < _n; i++ )
			{
				if( i + GetBitCount( i ) == _n )
				{
					isEnable = true;
					break;
				}
			}
			if( !isEnable )
			{
				Debug.Print( ( -1 ).ToString() );
				Console.WriteLine( ( -1 ) );
				return;
			}

			var result = Move( _n, 1, new List<int>(), int.MaxValue );
			Debug.Print( ( result < int.MaxValue ? result : -1 ).ToString() );
			Console.WriteLine( ( result < int.MaxValue ? result : -1 ).ToString() );
		}

		private static int Move( int n, int index, List<int> movedIndexes, int moveCount )
		{
			// ゴールに到達した場合は処理を終了する
			// ※初っ端がゴールだった場合を考慮
			if( index == n )
				return moveCount == int.MaxValue ? 1 : moveCount + 1;

			// 現在位置から先に進んだ場合と後に戻った場合をそれぞれチェック
			var moveLength = GetBitCount( index );
			var caseForward = int.MaxValue;
			var caseBackward = int.MaxValue;

			// 一度辿った道に移動してしまう場合は処理しない
			// 範囲外となる場合も処理しない
			var forward = index + moveLength;
			if( !movedIndexes.Contains( forward ) && forward <= n )
				caseForward = Move( n, forward, movedIndexes.ToList(), ( moveCount == int.MaxValue ? 0 : moveCount ) + 1 );

			// 先に進んだケースで値が取得できた場合はその時点で処理を終了する
			// ※戻るケースは必ず１手余分に増えるので
			if( caseForward < int.MaxValue )
				return caseForward;

			var backward = index - moveLength;
			if( !movedIndexes.Contains( backward ) && backward > 0 )
				caseBackward = Move( n, backward, movedIndexes.ToList(), ( moveCount == int.MaxValue ? 0 : moveCount ) + 1 );

			var result = caseForward < caseBackward ? caseForward : caseBackward;
			return result;
		}

		private static int GetBitCount( int target )
		{
			var bitCount = 0;
			for( ; target > 0; target &= ( target - 1 ) )
				bitCount++;
			return bitCount;
		}
	}
}
0