結果
問題 | No.3 ビットすごろく |
ユーザー | 明智重蔵 |
提出日時 | 2015-07-20 20:28:34 |
言語 | C#(csc) (csc 3.9.0) |
結果 |
AC
|
実行時間 | 334 ms / 5,000 ms |
コード長 | 3,008 bytes |
コンパイル時間 | 3,029 ms |
コンパイル使用メモリ | 107,028 KB |
実行使用メモリ | 65,004 KB |
最終ジャッジ日時 | 2023-09-13 23:17:05 |
合計ジャッジ時間 | 8,909 ms |
ジャッジサーバーID (参考情報) |
judge15 / judge12 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 64 ms
19,492 KB |
testcase_01 | AC | 63 ms
21,532 KB |
testcase_02 | AC | 63 ms
21,544 KB |
testcase_03 | AC | 71 ms
23,976 KB |
testcase_04 | AC | 64 ms
21,444 KB |
testcase_05 | AC | 122 ms
49,232 KB |
testcase_06 | AC | 70 ms
30,604 KB |
testcase_07 | AC | 66 ms
27,736 KB |
testcase_08 | AC | 89 ms
43,128 KB |
testcase_09 | AC | 177 ms
49,364 KB |
testcase_10 | AC | 256 ms
56,100 KB |
testcase_11 | AC | 154 ms
51,020 KB |
testcase_12 | AC | 120 ms
49,820 KB |
testcase_13 | AC | 70 ms
27,888 KB |
testcase_14 | AC | 252 ms
56,384 KB |
testcase_15 | AC | 318 ms
62,772 KB |
testcase_16 | AC | 290 ms
59,848 KB |
testcase_17 | AC | 308 ms
62,980 KB |
testcase_18 | AC | 68 ms
27,720 KB |
testcase_19 | AC | 334 ms
62,980 KB |
testcase_20 | AC | 64 ms
21,540 KB |
testcase_21 | AC | 64 ms
21,604 KB |
testcase_22 | AC | 253 ms
56,344 KB |
testcase_23 | AC | 325 ms
65,004 KB |
testcase_24 | AC | 328 ms
60,780 KB |
testcase_25 | AC | 316 ms
60,860 KB |
testcase_26 | AC | 59 ms
21,524 KB |
testcase_27 | AC | 67 ms
23,852 KB |
testcase_28 | AC | 280 ms
58,100 KB |
testcase_29 | AC | 160 ms
50,744 KB |
testcase_30 | AC | 63 ms
21,424 KB |
testcase_31 | AC | 63 ms
21,508 KB |
testcase_32 | AC | 143 ms
48,436 KB |
コンパイルメッセージ
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.Generic; using System.Linq; class Program { static string InputPattern = "Input4"; static List<string> GetInputList() { var WillReturn = new List<string>(); if (InputPattern == "Input1") { WillReturn.Add("5"); } else if (InputPattern == "Input2") { WillReturn.Add("11"); } else if (InputPattern == "Input3") { WillReturn.Add("4"); } else { string wkStr; while ((wkStr = Console.ReadLine()) != null) WillReturn.Add(wkStr); } return WillReturn; } struct JyoutaiDef { internal int Level; internal int CurrInd; internal string Path; } static void Main() { List<string> InputList = GetInputList(); //すごろくのマスの数 int MasuCnt = int.Parse(InputList[0]); //各マスの1のビット数の配列 int[] BitCntArr = new int[MasuCnt]; for (int I = 1; I <= BitCntArr.GetUpperBound(0); I++) { int wkBitCnt = Convert.ToString(I, 2).ToCharArray().Count(X => X == '1'); BitCntArr[I] = wkBitCnt; } //場所ごとの最短手数 var MinLevelDict = new Dictionary<int, int>(); var stk = new Stack<JyoutaiDef>(); JyoutaiDef WillPush; WillPush.Level = 1; WillPush.CurrInd = 1; WillPush.Path = "1"; stk.Push(WillPush); int AnswerLevel = int.MaxValue; bool FoundAnswer = false; while (stk.Count > 0) { JyoutaiDef Popped = stk.Pop(); int CurrInd = Popped.CurrInd; //クリア判定 if (CurrInd == MasuCnt) { FoundAnswer = true; AnswerLevel = Popped.Level; //Console.WriteLine("{0}手の解候補。{1}を発見", Popped.Level, Popped.Path); continue; } //レベル制限 if (AnswerLevel <= Popped.Level + 1) continue; //Push処理 Action<int> PushSyori = (pNewInd) => { if (pNewInd < 1) return; if (MasuCnt < pNewInd) return; WillPush.Level = Popped.Level + 1; WillPush.CurrInd = pNewInd; //場所ごとの最短手数でなければ枝切り if (MinLevelDict.ContainsKey(WillPush.CurrInd)) { if (MinLevelDict[WillPush.CurrInd] <= WillPush.Level) { return; } } MinLevelDict[WillPush.CurrInd] = WillPush.Level; WillPush.Path = Popped.Path + "->" + pNewInd.ToString(); stk.Push(WillPush); }; PushSyori(CurrInd - BitCntArr[CurrInd]); PushSyori(CurrInd + BitCntArr[CurrInd]); } Console.WriteLine(FoundAnswer ? AnswerLevel : -1); } }