結果

問題 No.233 めぐるはめぐる (3)
コンテスト
ユーザー 14番
提出日時 2016-07-19 21:35:47
言語 C#(csc)
(csc 3.9.0)
結果
MLE  
(最新)
AC  
(最初)
実行時間 -
コード長 3,795 bytes
コンパイル時間 2,050 ms
コンパイル使用メモリ 116,092 KB
実行使用メモリ 148,172 KB
最終ジャッジ日時 2024-10-15 17:25:18
合計ジャッジ時間 14,268 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample MLE * 3
other MLE * 11
権限があれば一括ダウンロードができます
コンパイルメッセージ
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.Text;
using System.Linq;



class Program
{
    public void Proc()
    {
        Reader.IsDebug = false;
        string org = "inabameguru";
        char[] boin = org.Where(a=> a=='a' || a=='i' || a=='u' || a=='e' || a=='o').ToArray();
        char[] shiin = org.Where(a=> a!='a' && a!='i' && a!='u' && a!='e' && a!='o').ToArray();
        List<string> ret = this.GetKumiawase(boin, shiin, 0, false);
        Dictionary<String, bool> nameDic = new Dictionary<String, bool>();
        ret.ForEach(a=>nameDic[a] = true);
        // Console.WriteLine(nameDic.Count);
        int queryCount = int.Parse(Reader.ReadLine());
        for(int i=0; i<queryCount; i++) {
            string inpt = Reader.ReadLine();
            nameDic[inpt] = false;
        }
        if(nameDic.Count(a=>a.Value == true) == 0) {
            Console.WriteLine("NO");
        } else {
            Console.WriteLine(nameDic.First(a=>a.Value).Key);
        }
    }

    private Dictionary<int, Dictionary<bool, List<string>>> dic = new Dictionary<int, Dictionary<bool, List<string>>>();
    private List<String> GetKumiawase(char[] boin, char[] siin, int target,bool prevSiin) {
        if(!dic.ContainsKey(target)) {
            dic.Add(target, new Dictionary<bool, List<string>>());
        }
        if(dic[target].ContainsKey(prevSiin)) {
            return dic[target][prevSiin];
        }
        int boinCount = 0;
        for(int i=0; i<boin.Length; i++) {
            if((target & 1<<i) == 0) {
                boinCount++;
            }
        }
        int siinCount = 0;
        for(int i=0; i<siin.Length; i++) {
            if((target & 1<<(i+boin.Length))==0) {
                siinCount++;
            }
        }
        List<string> ans = new List<string>();
        
        if(boinCount == 1 && siinCount == 0) {
            for(int i=0; i<boin.Length; i++) {
                if((target & (1<<i)) == 0) {
                    ans.Add(boin[i].ToString());
                    break;
                }
            }
        } else {
            if(prevSiin || boinCount > siinCount) {
                for(int i=0; i<boin.Length; i++) {
                    if((target & 1<<i) == 0) {
                        List<string> ret = this.GetKumiawase(boin, siin, target + (1<<i), false);
                        if(ret != null && ret.Count > 0) {
                            ret.ForEach(a=>ans.Add(boin[i].ToString() + a));
                        }
                    }
                }
            }
            if(!prevSiin) {
                for(int i=0; i<siin.Length; i++) {
                    if((target & 1<<(i+boin.Length)) == 0) {
                        List<string> ret = this.GetKumiawase(boin, siin, target + (1<<(i+boin.Length)), true);
                        if(ret != null && ret.Count > 0) {
                            ret.ForEach(a=>ans.Add(siin[i].ToString() + a));
                        }
                    }
                } 
            }
        }
        this.dic[target].Add(prevSiin, ans);
        return ans;
    }

    public class Reader
    {
        public static bool IsDebug = true;
        private static String PlainInput = @"

3
inabameguru
meguruinaba
nemuriugaba


";
        private static System.IO.StringReader Sr = null;
        public static string ReadLine()
        {
            if (IsDebug)
            {
                if (Sr == null)
                {
                    Sr = new System.IO.StringReader(PlainInput.Trim());
                }
                return Sr.ReadLine();
            }
            else
            {
                return Console.ReadLine();
            }
        }
    }
    static void Main()
    {
        Program prg = new Program();
        prg.Proc();
    }
}
0