結果
| 問題 | 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 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| other | AC * 2 |
コンパイルメッセージ
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());
}
}