結果

問題 No.3 ビットすごろく
コンテスト
ユーザー velfare_nagata
提出日時 2016-10-05 01:34:47
言語 C#(csc)
(csc 3.9.0)
結果
TLE  
実行時間 -
コード長 2,999 bytes
コンパイル時間 4,869 ms
コンパイル使用メモリ 105,344 KB
実行使用メモリ 85,740 KB
最終ジャッジ日時 2024-11-21 17:05:14
合計ジャッジ時間 57,401 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 9 WA * 15 TLE * 9
権限があれば一括ダウンロードができます
コンパイルメッセージ
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>
		/// 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 = 5;
			var index = 1;
			var beforeIndex = index;
			var moveCount = 1;
			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;

			// 現在位置から先に進んだ場合と後に戻った場合をそれぞれチェック
			movedIndexes.Add( index );
			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 );

			return caseForward < caseBackward ? caseForward : caseBackward;
		}

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