結果

問題 No.506 限られたジャパリまん
コンテスト
ユーザー 14番
提出日時 2017-04-24 16:56:52
言語 C#(csc)
(csc 3.9.0)
結果
TLE  
実行時間 -
コード長 5,547 bytes
コンパイル時間 1,048 ms
コンパイル使用メモリ 110,208 KB
実行使用メモリ 51,968 KB
最終ジャッジ日時 2024-06-28 04:17:03
合計ジャッジ時間 4,636 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 4 TLE * 1 -- * 20
権限があれば一括ダウンロードができます
コンパイルメッセージ
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.Linq;
    using System.Collections.Generic;
    using System.Text.RegularExpressions;
    using System.Text;
     
    public class Program
    {
        public void Proc() {
            Reader.IsDebug = false;
            int[] inpt = Reader.ReadLine().Split(' ').Select(a=>int.Parse(a)).ToArray();

            int h = inpt[1];
            int w = inpt[0];

            int fCount = inpt[2];
            int jCount = inpt[3];

            for(int i=0; i<fCount; i++) {
                this.FrList.Add(new Fr(i, Reader.ReadLine()));
            }
            long[,] map = new long[w+1,h+1];
            for(int x=0; x<=w; x++) {
                for(int y=0; y<=h; y++) {
                    if(this.FrList.Any(a=>a.X == x && a.Y == y)) {
                        map[x,y] = 0;
                    } else if(x == 0 && y==0) {
                        map[0,0] = 1;
                    } else {
                        long tmp = 0;
                        if(x>0) {
                            tmp+=map[x-1,y];
                        }
                        if(y>0) {
                            tmp+=map[x,y-1];
                        }
                        map[x,y] = tmp;
                    }
                }
            }
            Ans ans = GetAns(0,map, jCount);
            Console.WriteLine(ans.WayCount);
            for(int i=0; i<this.FrList.Count; i++) {
                if(((1<<i)&ans.Flag)>0) {
                    Console.WriteLine(FrList[i].Name);
                }
            }
            
        }

        private struct Ans {
            public long WayCount;
            public int Flag;

            public Ans(long w, int f) {
                this.WayCount = w;
                this.Flag = f;
            }
        }
        
        private Ans GetAns(int flag, long[,] map, int remain) {
            if(dic.ContainsKey(flag)) {
                return dic[flag];
            }
            if(remain <= 0) {
                return new Ans(map[map.GetLength(0)-1, map.GetLength(1)-1], flag);
            }
            Ans ans = new Ans(0,0);

            for(int i=0; i<FrList.Count; i++) {
                int key = 1<<i;
                if(FrList[i].Kaitsu(map) == 0) {
                    continue;
                }
                if((flag&key)>0) {
                    continue;
                }
                long[,] subMap = new long[map.GetLength(0), map.GetLength(1)];

                subMap[FrList[i].X, FrList[i].Y] = FrList[i].Kaitsu(map);

                for(int x=0; x<map.GetLength(0); x++) {
                    for(int y=0; y<map.GetLength(1);y++) {
                        if(map[x,y] == 0) {
                            if(this.FrList.Any(a=>a.X == x&&a.Y==y)) {
                                int k = 1<<this.FrList.Find(a=>a.X == x && a.Y == y).ID;
                                if(k!=key && (flag&k)==0) {
                                    continue;
                                }
                            }
                        }
                        if(x==0&&y==0) {
                            subMap[0,0] = map[0,0];
                        } else {
                            long tmp = 0;
                            if(x>0) {
                                tmp+=subMap[x-1,y];
                            }
                            if(y>0) {
                                tmp+=subMap[x,y-1];
                            }
                            subMap[x,y] = tmp;
                        }
                    }
                }
                Ans ret = GetAns(flag+key, subMap, remain-1);
                if(ret.WayCount > ans.WayCount) {
                    ans = ret;
                }
            }
            dic[flag] = ans;
            return ans;
        }

        private List<Fr> FrList = new List<Fr>();

        private const long ModNum = 1000000000 + 1;

        private Dictionary<int, Ans> dic = new Dictionary<int, Ans>();


        private class Fr {
            public int X;
            public int Y;

            public int ID;
            public String Name;

            public long Kaitsu(long[,] mp) {
                long ret = 0;
                if(this.X == 0 && this.Y == 0) {
                    return 1;
                }
                if(this.X > 0) {
                    ret = mp[this.X-1, this.Y];
                }
                if(this.Y > 0) {
                    ret += mp[this.X, this.Y-1];
                }
                return ret;
            }

            public Fr(int id, String init) {
                string[] spl = init.Split(' ');
                this.ID = id;
                this.X = int.Parse(spl[0]);
                this.Y = int.Parse(spl[1]);
                this.Name = spl[2];
            }
        }

        public class Reader {
            public static bool IsDebug = true;
            private static System.IO.StringReader SReader;
            private static string InitText = @"




3 4 2 0
3 3 konoha
2 4 mimi




";
            public static string ReadLine() {
                if(IsDebug) {
                    if(SReader == null) {
                        SReader = new System.IO.StringReader(InitText.Trim());
                    }
                    return SReader.ReadLine();
                } else {
                    return Console.ReadLine();
                }
            }
        }
        public static void Main(string[] args)
        {
            Program prg = new Program();
            prg.Proc();
        }
    }
0