結果

問題 No.3 ビットすごろく
ユーザー velfare_nagatavelfare_nagata
提出日時 2016-10-05 01:55:30
言語 C#(csc)
(csc 3.9.0)
結果
WA  
実行時間 -
コード長 3,310 bytes
コンパイル時間 834 ms
コンパイル使用メモリ 114,452 KB
実行使用メモリ 719,444 KB
最終ジャッジ日時 2024-05-01 12:40:24
合計ジャッジ時間 8,050 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge3
このコードへのチャレンジ
（要ログイン）

テストケース

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