#62024 (C#(csc)) No.233 めぐるはめぐる (3)

• 問題: No.233 めぐるはめぐる (3)
• ユーザー: nuwasogi
• 提出日時: 2015-12-02 05:12:25
• 言語: C#(csc) (csc 3.9.0)
• 結果: TLE
• 実行時間: -
• コード長: 5,844 bytes
• コンパイル時間: 3,502 ms
• コンパイル使用メモリ: 112,128 KB
• 実行使用メモリ: 60,428 KB
• 最終ジャッジ日時: 2024-09-14 07:49:26
• 合計ジャッジ時間: 6,036 ms
• ジャッジサーバーID （参考情報）: judge1 / judge5

ファイルパターン	結果
sample	-- * 3
other	TLE * 1 -- * 10

コンパイルメッセージ

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;

namespace Meguru_ha_Meguru_CS
{
    class Program
    {
        static void Main(string[] args)
        {
            Solver sol = new Solver();
            sol.Solve();
        }
    }

    class Solver
    {
        int N;
        const int N_MAX = 129600;
        HashSet<string> usedNames; // 使用済み名前
        HashSet<string> usedNamesConstants; // 使用済み子音列
        HashSet<string> constants; // 全子音列
        HashSet<string> vowels; // 全母音列
        HashSet<string> postpone; // 後回しにする子音列
        string originalconstant = "nbmgr";
        string originalvowel = "iaaeuu";

        public void Solve()
        {
            if (N == N_MAX)
            {
                Console.WriteLine("NO");
                return;
            }
            if (N == 0)
            {
                Console.WriteLine("inabameguru");
                return;
            }
            // 各子音列について
            foreach (char[] c in Permutation.Enumurate(originalconstant))
            {
                string sc = new string(c);
                // 既に使用されている子音列の場合は後回し
                if (usedNamesConstants.Contains(sc))
                {
                    postpone.Add(sc);
                    continue;
                }
                // 各母音列について
                foreach (string sv in vowels)
                {
                    // 各ローマ字読み可能な文字列について
                    foreach (string name in RomanReadable(sc, sv))
                    {
                        if (!usedNames.Contains(name))
                        {
                            Console.WriteLine(name);
                            return;
                        }
                    }
                }
            }
            // 後回しにしたもの
            foreach (string sc in postpone)
            {
                // 各母音列について
                foreach (string sv in vowels)
                {
                    // 各ローマ字読み可能な文字列について
                    foreach (string name in RomanReadable(sc, sv))
                    {
                        if (!usedNames.Contains(name))
                        {
                            Console.WriteLine(name);
                            return;
                        }
                    }
                }
            }
        }

        public Solver()
        {
            N = ri();
            usedNames = new HashSet<string>();
            usedNamesConstants = new HashSet<string>();
            constants = new HashSet<string>();
            vowels = new HashSet<string>();
            postpone = new HashSet<string>();
            for (int i = 0; i < N; i++)
            {
                string s = rs();
                usedNames.Add(s);
                usedNamesConstants.Add(GetConstant(s));
                List<char> ca = new List<char>(originalvowel.Length);
                foreach (int[] ia in Permutation.Enumurate(Enumerable.Range(0, originalvowel.Length)))
                {
                    for (int j = 0; j < originalvowel.Length; j++)
                    {
                        ca.Add(originalvowel[ia[j]]);
                    }
                    vowels.Add(new string(ca.ToArray()));
                }
            }
        }
        /* 子音部分を返す */
        string GetConstant(string s)
        {
            return new String(s.Where(c => c != 'a' && c != 'e' && c != 'i' && c != 'u').ToArray());
        }
        /* ローマ字読み可能な文字列を返すイテレータ */
        static IEnumerable<string> RomanReadable(string cons, string vows)
        {
            for (int i = 0; i < 6; i++)
            {
                List<char> res = new List<char>(11);
                for (int j = 0; j < i; j++)
                {
                    res.Add(cons[j]);
                    res.Add(vows[j]);
                }
                res.Add(vows[i]);
                for (int j = i; j < 5; j++)
                {
                    res.Add(cons[j]);
                    res.Add(vows[j + 1]);
                }
                yield return new string(res.ToArray());
            }
        }

        static String rs() { return Console.ReadLine(); }
        static int ri() { return int.Parse(Console.ReadLine()); }
        static long rl() { return long.Parse(Console.ReadLine()); }
        static double rd() { return double.Parse(Console.ReadLine()); }
        static String[] rsa() { return Console.ReadLine().Split(' '); }
        static int[] ria() { return Console.ReadLine().Split(' ').Select(e => int.Parse(e)).ToArray(); }
        static long[] rla() { return Console.ReadLine().Split(' ').Select(e => long.Parse(e)).ToArray(); }
        static double[] rda() { return Console.ReadLine().Split(' ').Select(e => double.Parse(e)).ToArray(); }
    }

    static class Permutation
    {
        public static IEnumerable<T[]> Enumurate<T>(IEnumerable<T> nums)
        {
            return _GetPermutations<T>(new List<T>(), nums.ToList());
        }
        static IEnumerable<T[]> _GetPermutations<T>(IEnumerable<T> perm, IEnumerable<T> nums)
        {
            if (nums.Count() == 0)
            {
                yield return perm.ToArray();
            }
            else
            {
                foreach (var n in nums)
                {
                    var result = _GetPermutations<T>(perm.Concat(new T[] { n }), nums.Where(x => x.Equals(n) == false));
                    foreach (var xs in result)
                    {
                        yield return xs.ToArray();
                    }
                }
            }
        }
    }
}