結果

問題 No.3 ビットすごろく
ユーザー masaktmasakt
提出日時 2017-04-03 01:55:11
言語 C#(csc)
(csc 3.9.0)
結果
AC  
実行時間 1,349 ms / 5,000 ms
コード長 3,035 bytes
コンパイル時間 998 ms
コンパイル使用メモリ 114,080 KB
実行使用メモリ 153,876 KB
最終ジャッジ日時 2024-07-01 08:40:08
合計ジャッジ時間 19,935 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge4
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 44 ms
26,940 KB
testcase_01 AC 43 ms
26,796 KB
testcase_02 AC 44 ms
24,632 KB
testcase_03 AC 130 ms
39,436 KB
testcase_04 AC 54 ms
27,696 KB
testcase_05 AC 429 ms
61,728 KB
testcase_06 AC 147 ms
40,212 KB
testcase_07 AC 82 ms
36,232 KB
testcase_08 AC 297 ms
53,524 KB
testcase_09 AC 699 ms
90,412 KB
testcase_10 AC 942 ms
132,048 KB
testcase_11 AC 598 ms
83,768 KB
testcase_12 AC 410 ms
58,920 KB
testcase_13 AC 111 ms
37,892 KB
testcase_14 AC 897 ms
95,160 KB
testcase_15 AC 1,316 ms
150,592 KB
testcase_16 AC 1,146 ms
143,576 KB
testcase_17 AC 1,275 ms
150,512 KB
testcase_18 AC 92 ms
36,620 KB
testcase_19 AC 1,343 ms
153,876 KB
testcase_20 AC 51 ms
27,456 KB
testcase_21 AC 45 ms
26,796 KB
testcase_22 AC 884 ms
98,124 KB
testcase_23 AC 1,349 ms
151,924 KB
testcase_24 AC 1,345 ms
151,956 KB
testcase_25 AC 1,317 ms
152,308 KB
testcase_26 AC 43 ms
26,540 KB
testcase_27 AC 118 ms
38,276 KB
testcase_28 AC 1,106 ms
143,428 KB
testcase_29 AC 612 ms
86,948 KB
testcase_30 AC 46 ms
24,756 KB
testcase_31 AC 46 ms
27,100 KB
testcase_32 AC 533 ms
80,580 KB
権限があれば一括ダウンロードができます
コンパイルメッセージ
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.Generic;
using System.Linq;

class P
{
    static int Search(int goal)
    {
        Random r = new Random((int)DateTime.Now.Ticks);
        int x = 1;
        int c = 1;
        int step = 1;
        KeyValuePair<int, int> post;
        KeyValuePair<int, int> pre;
        path.Add(new KeyValuePair<int, int>(x, c));
        minX[x] = Math.Min(1, c);
        memo[x][1] = true;

        if (x == goal)
        {
            return 1;
        }

        while (path.Count != 0)
        {
            if (x == goal)
            {
                return c;
            }
            else
            {
                KeyValuePair<int, int> p = path.First();
                x = p.Key;
                c = p.Value;
                path.Remove(path.First());
                step = Convert.ToString(x, 2).Replace("0", "").Length;
                post = new KeyValuePair<int, int>(x + step, c + 1);
                pre = new KeyValuePair<int, int>(x - step, c + 1);
                if (1 <= post.Key && post.Key <= goal)
                {
                    if (!path.Contains(post))
                    {
                        if (minX[post.Key] == -1)
                        {
                            minX[post.Key] = post.Value;
                        }
                        else
                        {
                            minX[post.Key] = Math.Min(minX[post.Key], post.Value);
                        }
                        if (!memo[x][post.Key])
                        {
                            path.Add(new KeyValuePair<int, int>(post.Key, minX[post.Key]));
                            memo[x][post.Key] = true;
                        }
                    }
                }
                if (1 <= pre.Key && pre.Key <= goal)
                {
                    if (!path.Contains(pre))
                    {
                        if (minX[pre.Key] == -1)
                        {
                            minX[pre.Key] = pre.Value;
                        }
                        else
                        {
                            minX[pre.Key] = Math.Min(minX[pre.Key], pre.Value);
                        }

                        if (!memo[x][pre.Key])
                        {
                            path.Add(new KeyValuePair<int, int>(pre.Key, minX[pre.Key]));
                            memo[x][pre.Key] = true;
                        }
                    }
                }
            }
        }
        return -1;
    }
    static bool[][] memo;
    static int[] minX;
    static List<KeyValuePair<int, int>> path = new List<KeyValuePair<int, int>>();

    static void Main()
    {
        int n = int.Parse(Console.ReadLine());
        memo = new bool[n+1][];
        for (int i = 0; i < memo.Length; i++)
        {
            memo[i] = Enumerable.Range(0, n+1).Select(a => false).ToArray();
        }
        minX = Enumerable.Range(0, n+1).Select(a => -1).ToArray();
        Console.WriteLine(Search(n));
    }
}
0