#121702 (C#(csc)) No.3 ビットすごろく

• 問題: 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

入力	結果	実行時間; 実行使用メモリ
testcase_00	AC	26 ms; 58,296 KB
testcase_01	AC	26 ms; 23,552 KB
testcase_02	AC	25 ms; 33,248 KB
testcase_03	TLE	-
testcase_04	AC	26 ms; 23,936 KB
testcase_05	TLE	-
testcase_06	TLE	-
testcase_07	AC	27 ms; 70,176 KB
testcase_08	WA	-
testcase_09	WA	-
testcase_10	WA	-
testcase_11	WA	-
testcase_12	TLE	-
testcase_13	TLE	-
testcase_14	TLE	-
testcase_15	TLE	-
testcase_16	WA	-
testcase_17	WA	-
testcase_18	AC	27 ms; 19,328 KB
testcase_19	WA	-
testcase_20	WA	-
testcase_21	AC	25 ms; 18,432 KB
testcase_22	TLE	-
testcase_23	TLE	-
testcase_24	WA	-
testcase_25	WA	-
testcase_26	AC	24 ms; 18,304 KB
testcase_27	WA	-
testcase_28	WA	-
testcase_29	WA	-
testcase_30	WA	-
testcase_31	AC	26 ms; 18,176 KB
testcase_32	WA	-

コンパイルメッセージ

Microsoft (R) Visual C# Compiler version 3.9.0-6.21124.20 (db94f4cc)
Copyright (C) Microsoft Corporation. All rights reserved.

ソースコード

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;
		}
	}
}