結果

問題 No.3 ビットすごろく
ユーザー masaktmasakt
提出日時 2017-04-03 01:55:11
言語 C#(csc)
(csc 3.9.0)
結果
AC  
実行時間 1,386 ms / 5,000 ms
コード長 3,035 bytes
コンパイル時間 2,350 ms
コンパイル使用メモリ 110,028 KB
実行使用メモリ 151,488 KB
最終ジャッジ日時 2023-09-14 00:39:59
合計ジャッジ時間 23,128 ms
ジャッジサーバーID
（参考情報） 		judge11 / judge15
このコードへのチャレンジ（β）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 112 ms
26,532 KB
testcase_01 AC 112 ms
26,644 KB
testcase_02 AC 112 ms
24,508 KB
testcase_03 AC 196 ms
37,036 KB
testcase_04 AC 121 ms
25,128 KB
testcase_05 AC 490 ms
55,024 KB
testcase_06 AC 213 ms
37,872 KB
testcase_07 AC 148 ms
31,496 KB
testcase_08 AC 360 ms
53,252 KB
testcase_09 AC 753 ms
86,260 KB
testcase_10 AC 990 ms
129,868 KB
testcase_11 AC 655 ms
79,180 KB
testcase_12 AC 477 ms
58,456 KB
testcase_13 AC 174 ms
35,620 KB
testcase_14 AC 952 ms
94,452 KB
testcase_15 AC 1,343 ms
147,980 KB
testcase_16 AC 1,177 ms
139,572 KB
testcase_17 AC 1,306 ms
148,328 KB
testcase_18 AC 159 ms
31,824 KB
testcase_19 AC 1,367 ms
151,488 KB
testcase_20 AC 117 ms
27,100 KB
testcase_21 AC 111 ms
24,560 KB
testcase_22 AC 929 ms
91,772 KB
testcase_23 AC 1,386 ms
149,484 KB
testcase_24 AC 1,373 ms
149,668 KB
testcase_25 AC 1,340 ms
150,212 KB
testcase_26 AC 106 ms
24,540 KB
testcase_27 AC 185 ms
31,832 KB
testcase_28 AC 1,137 ms
139,072 KB
testcase_29 AC 672 ms
82,268 KB
testcase_30 AC 113 ms
26,612 KB
testcase_31 AC 114 ms
26,800 KB
testcase_32 AC 590 ms
78,116 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