#79293 (C#(csc)) No.234 めぐるはめぐる (4)

• 問題: No.234 めぐるはめぐる (4)
• ユーザー: 古寺いろは
• 提出日時: 2016-02-29 03:08:20
• 言語: C#(csc) (csc 3.9.0)
• 結果: AC
• 実行時間: 25 ms / 1,000 ms
• コード長: 8,143 bytes
• コンパイル時間: 980 ms
• コンパイル使用メモリ: 116,168 KB
• 実行使用メモリ: 24,012 KB
• 最終ジャッジ日時: 2024-09-24 12:40:19
• 合計ジャッジ時間: 1,526 ms
• ジャッジサーバーID （参考情報）: judge1 / judge3

入力	結果	実行時間; 実行使用メモリ
testcase_00	AC	25 ms; 24,012 KB
testcase_01	AC	25 ms; 24,004 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;
using System.Collections.Generic;
using System.Linq;
using System.IO;
using System.Text;
using System.Numerics;

class Meguru
{

    public Meguru() { }
    public static int Main()
    {
        new Meguru().calc();
        return 0;
    }


    string[] StringAns =
    {
        "0",
        "1",
        "11",
        "110",
        "2402",
        "128967",
        "16767653",
        "5436906668",
        "4406952731948",
        "8819634719356421",
        "43329348004927734247",
        "522235268182347360718818",
        "15436131339319739257518081878"
    };

    void calc()
    {
        cin = new Scanner();
        int N = cin.nextInt();
        Console.WriteLine(StringAns[N]);
    }

    Scanner cin;

    BigInteger ans;

    Dictionary<string, BigInteger> dp;
    Dictionary<string, BigInteger> nextdp;


    string SetString(string a)
    {
        char[] ans = a.ToCharArray();
        Dictionary<char, char> cdic = new Dictionary<char, char>();
        cdic['0'] = '0';
        cdic['9'] = '9';
        int count = 0;
        for (int i = 0; i < ans.Length; i++)
        {
            if (ans[i] == ',') continue;
            if (!cdic.ContainsKey(ans[i]))
            {
                cdic[ans[i]] = (char)('1' + count++);
            }
            ans[i] = cdic[ans[i]];
        }
        return new string(ans);
    }

    void updatenextdp(int i, int j, string prea, string preb, int t1, int t2, int t3, string r1 = "", string r2 = "")
    {
        if (t1 >= 1 && t1 <= 8) return;

        string pre = prea + "," + preb;
        string nexta = prea.Substring(1);
        string nextb = preb.Substring(0, preb.Length - 1) + t2 + "" +  t3;
        string next = nexta + "," + nextb;
        if (r1 != "") next = next.Replace(r1, r2);

        next = SetString(next);

        if (next.IndexOf("1") == -1 && (t1 != 0 || t2 != 0 || t3 != 0))
        {
            ans += dp[pre];
        }
        else
        {
            if (!nextdp.ContainsKey(next)) nextdp[next] = 0;
            nextdp[next] += dp[pre];
        }
    }

    void calc2()
    {
        cin = new Scanner();
        int N = cin.nextInt();

        ans = 0;

        dp = new Dictionary<string,BigInteger>();
        dp["0,0"] = 1;

        for (int i = 0; i < N; i++)
        {
            for (int j = 0; j <= i; j++)
            {
                nextdp = new Dictionary<string, BigInteger>();
                ans++;
                //△ 左下1 左上2 右下3
                foreach (var pre in dp.Keys)
                {
                    string[] prearray = pre.Split(',');
                    string prea = prearray[0];
                    string preb = prearray[1];

                    int type1 = prea[0] - '0';
                    int type2 = preb[j] - '0';

                    bool check = pre.IndexOf('2') == -1;

                    //1-2閉じる
                    if (type1 != 0 && type2 != 0 && type1 != 9 && type2 != 9 && ((type1 != type2) || check))
                    {
                        int t1 = 9;
                        int t2 = 9;
                        int t3 = 0;
                        updatenextdp(i, j, prea, preb, t1, t2, t3, type1 + "", type2 + "");
                        //3経由する
                        t3 = 9;
                        updatenextdp(i, j, prea, preb, t1, t2, t3, type1 + "", type2 + "");
                    }

                    //1to2
                    if (type1 != 0 && type1 != 9 && type2 == 0)
                    {
                        int t1 = 9;
                        int t2 = type1;
                        int t3 = 0;

                        //3経由しない
                        updatenextdp(i, j, prea, preb, t1, t2, t3);

                        //3経由する
                        t3 = 9;
                        updatenextdp(i, j, prea, preb, t1, t2, t3);
                    }

                    //1to3
                    if (type1 != 0 && type1 != 9)
                    {
                        int t1 = 9;
                        int t2 = type2;
                        int t3 = type1;

                        //2経由しない
                        updatenextdp(i, j, prea, preb, t1, t2, t3);

                        //2経由する
                        if (type2 == 0)
                        {
                            t2 = 9;
                            updatenextdp(i, j, prea, preb, t1, t2, t3);
                        }
                    }

                    //2to3
                    if (type2 != 0 && type2 != 9)
                    {
                        int t1 = type1;
                        int t2 = 9;
                        int t3 = type2;

                        //1経由しない
                        updatenextdp(i, j, prea, preb, t1, t2, t3);

                        //1経由する
                        if (type1 == 0)
                        {
                            t1 = 9;
                            updatenextdp(i, j, prea, preb, t1, t2, t3);
                        }
                    }

                    //なにもしない
                    if (true)
                    {
                        int t1 = type1;
                        int t2 = type2;
                        int t3 = 0;
                        updatenextdp(i, j, prea, preb, t1, t2, t3);
                    }


                    //2-3で新規作成
                    if (type2 == 0)
                    {
                        //1経由しない
                        int t1 = type1;
                        int t2 = 8;
                        int t3 = 8;
                        updatenextdp(i, j, prea, preb, t1, t2, t3);

                        //1経由する
                        if (type1 == 0)
                        {
                            t1 = 9;
                            updatenextdp(i, j, prea, preb, t1, t2, t3);
                        }
                    }
                }
                dp = nextdp;
            }
            Console.WriteLine((i + 1) + " " + ans);

            nextdp = new Dictionary<string, BigInteger>();
            foreach (var item in dp)
            {
                string[] prearray = item.Key.Split(',');
                string preb = prearray[1];
                nextdp[preb + ",0"] = item.Value;
            }
            dp = nextdp;
        }


    }

    //swap
    void swap<T>(ref T a, ref T b)
    {
        T c = a;
        a = b;
        b = c;
    }

    public static bool next_permutation<T>(T[] array) where T : IComparable<T>
    {
        return next_permutation(array, 0, array.Length);
    }

    public static bool next_permutation<T>(T[] array, int start, int length) where T : IComparable<T>
    {
        int end = start + length - 1;
        if (end <= start) return false;
        int last = end;
        while (true)
        {
            int pos = last--;
            if (array[last].CompareTo(array[pos]) < 0)
            {
                int i;
                for (i = end + 1; array[last].CompareTo(array[--i]) >= 0; ) { }
                T tmp = array[last]; array[last] = array[i]; array[i] = tmp;
                Array.Reverse(array, pos, end - pos + 1);
                return true;
            }
            if (last == start)
            {
                //Array.Reverse(array, start, end - start);
                return false;
            }
        }
    }
        

}






class Scanner
{
    string[] s;
    int i;

    char[] cs = new char[] { ' ' };

    public Scanner()
    {
        s = new string[0];
        i = 0;
    }

    public string next()
    {
        if (i < s.Length) return s[i++];
        string st = Console.ReadLine();
        while (st == "") st = Console.ReadLine();
        s = st.Split(cs, StringSplitOptions.RemoveEmptyEntries);
        i = 0;
        return next();
    }

    public int nextInt()
    {
        return int.Parse(next());
    }

    public long nextLong()
    {
        return long.Parse(next());
    }

    public double nextDouble()
    {
        return double.Parse(next());
    }

}