結果
問題 |
No.3 ビットすごろく
|
ユーザー |
![]() |
提出日時 | 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.
ソースコード
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 ); // 先に進んだケースで値が取得できた場合はその時点で処理を終了する // ※戻るケースは必ず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; } } }