Submission #14695706


Source Code Expand

Copy
// ReSharper disable RedundantUsingDirective
// ReSharper disable CheckNamespace
// ReSharper disable PossibleNullReferenceException
// ReSharper disable AssignNullToNotNullAttribute
// ReSharper disable MemberCanBePrivate.Global
/*
https://atcoder.jp/contests/xxxx
*/

using System;
using System.Collections.Generic;
using System.Diagnostics;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
using System.IO;
using System.Security.Cryptography.X509Certificates;


namespace Marathon
{
    public class Program
    {
        public static void Main(string[] args)
        {
            SL.Run(args);
        }
    }

    public class SL
    {
        public static string Name = "Initial";
        public static bool DEBUG = false;
        public static bool MEASURE_TIME = false;

        public static Timer timer = new Timer();
        public static TimerStat timerStat = new TimerStat();
        public static long TL = 9000;

        public static Random rnd;
        private static TextReader reader;
        private static TextWriter writer;
        public static Logger logger;

        public static char[] MV = new char[] {'D', 'R', 'U', 'L'};
        public static int DR = 4;
        public static int[] DX = new int[] {0, 1, 0, -1};
        public static int[] DY = new int[] {1, 0, -1, 0};

        // 
        public static int H, W, K, sr, sc;
        public static char[,] M;
        public static int N;
        public static int[] FR, FC, FN, DN;

        // パラメータ
        public static int Seed;


        public static void Run(string[] args)
        {
            timer.Start();
#if LOCAL
            Directory.SetCurrentDirectory(
                Path.GetDirectoryName(System.Reflection.Assembly.GetExecutingAssembly().Location));
            Directory.CreateDirectory("result");
            reader = new StreamReader(@"input/example_02_in.txt");
            writer = new StreamWriter(@"result/example_02_out_my.txt");
            TL = 2500;
            DEBUG = true;
#else
            reader = Console.In;
            writer = Console.Out;
#endif
            timer.Start();

            // Input
            {
                {
                    var values = reader.ReadLine().Split(' ');
                    H = int.Parse(values[0]);
                    W = int.Parse(values[1]);
                    K = int.Parse(values[2]);
                    sr = int.Parse(values[3]) - 1;
                    sc = int.Parse(values[4]) - 1;
                }

                M = new char[H, W];
                for (int y = 0; y < H; y++)
                {
                    var values = reader.ReadLine();
                    for (int x = 0; x < W; x++)
                    {
                        M[y, x] = values[x];
                    }
                }

                N = int.Parse(reader.ReadLine());
                FR = new int[N];
                FC = new int[N];
                FN = new int[N];
                DN = new int[N];

                for (int i = 0; i < N; i++)
                {
                    var values = reader.ReadLine().Split(' ');
                    FR[i] = int.Parse(values[0]) - 1;
                    FC[i] = int.Parse(values[1]) - 1;
                    FN[i] = int.Parse(values[2]);
                    DN[i] = int.Parse(values[3]);
                }

                // マップに食物のセット
                for (int i = 0; i < N; i++)
                {
                    M[FR[i], FC[i]] = 'F';
                }
            }

            // Run
            logger = new Logger(DEBUG);
            var ret = Solve();
            // 長さが小さいときも、大きいときも許容する
            while (ret.Count < K)
                ret.Add('-');
            ret = ret.Take(K).ToList();

            // Output
            writer.WriteLine(string.Join("", ret));
            writer.Close();

            timerStat.Print();
        }

        static List<char> Solve()
        {
            var ret = new List<char>();
            int sy = sr;
            int sx = sc;
            
            while (true)
            {
                var map = new int[H, W];
                for (int y = 0; y < H; y++)
                for (int x = 0; x < W; x++)
                {
                    map[y, x] = -1;
                }

                int gy = -1;
                int gx = -1;
                var q = new Queue<Data>();
                q.Enqueue(new Data(sy, sx, 0));

                // 1回分の探索
                while (q.Count > 0)
                {
                    var data = q.Dequeue();
                    int y = data.y;
                    int x = data.x;
                    int d = data.d;
                    if (map[y, x] != -1)
                        continue;

                    map[y, x] = d;
                    if (M[y, x] == 'F')
                    {
                        gy = y;
                        gx = x;
                        M[y, x] = '.';
                        break;
                    }

                    for (int dr = 0; dr < DR; dr++)
                    {
                        int dy = DY[dr];
                        int dx = DX[dr];
                        int yy = y + dy;
                        int xx = x + dx;
                        if (0 <= yy && yy < H && 0 <= xx && xx < W)
                            if (M[yy, xx] != '#')
                                if (map[yy, xx] == -1)
                                {
                                    q.Enqueue(new Data(yy, xx, d + 1));
                                }
                    }
                }

                // 経路の復元
                if (gy != -1)
                {
                    var r = new List<char>();
                    int y = gy;
                    int x = gx;
                    int d = map[gy, gx];
                    Console.Error.WriteLine(map.Show());
                    while (d > 0)
                    {
                        for (int dr = 0; dr < DR; dr++)
                        {
                            int dy = DY[dr];
                            int dx = DX[dr];
                            int yy = y - dy;
                            int xx = x - dx;
                            if (0 <= yy && yy < H && 0 <= xx && xx < W)
                                if (map[yy, xx] == d - 1)
                                {
                                    r.Add(MV[dr]);
                                    d--;
                                    y = yy;
                                    x = xx;
                                    break;
                                }
                        }
                    }

                    r.Reverse();
                    ret.AddRange(r);

                    sy = gy;
                    sx = gx;
                }

                // 終了
                if (gy == -1 || ret.Count >= K)
                    return ret;
            }

            // timerStat.Stop(4);
            // logger.Info($"[RESULT]{{ \"name\":\"{Name}\"}}");
        }
    }

    static class Util
    {
        public static string Show<T>(this T[,] ary)
        {
            var sb = new StringBuilder();
            sb.AppendLine("---------------------");
            int h = ary.GetLength(0);
            int w = ary.GetLength(1);
            for (int y = 0; y < h; y++)
            {
                for (int x = 0; x < w; x++)
                {
                    sb.Append(ary[y, x]);
                    if (x < w)
                        sb.Append(',');
                }

                if (y < h)
                    sb.Append('\n');
            }
            sb.AppendLine("---------------------");

            return sb.ToString();
        }
    }
    // Data Struct
    struct Data
    {
        public int x;
        public int y;
        public int d;

        public Data(int y, int x, int d)
        {
            this.x = x;
            this.y = y;
            this.d = d;
        }

        // SortするときのComparerは明示的に指定する
        public static int CompareTo(Data d1, Data d2)
        {
            int result = d1.x.CompareTo(d2.x);
            if (result == 0)
                result = d1.y.CompareTo(d2.y);
            return result;
        }
    }

    // Utility -------------------------------------------
    public class Logger
    {
        public bool Verbose;
        private StreamWriter streamWriter;

        public Logger(bool verbose, string path = @"../../model/log.log")
        {
            Verbose = verbose;
            if (Verbose)
            {
                System.IO.Directory.CreateDirectory(Path.GetDirectoryName(path));
                streamWriter = new StreamWriter(path);
            }
        }

        public void Info(string message)
        {
            if (Verbose)
            {
                Console.Error.WriteLine(message);
                streamWriter.WriteLine(message);
            }
        }

        public void Debug(string message)
        {
            if (Verbose)
            {
                streamWriter.WriteLine(message);
            }
        }

        public void Close()
        {
            if (Verbose)
            {
                if (streamWriter != null)
                    streamWriter.Close();
            }
        }
    }

    public class Timer
    {
        private long StartTime;

        public static long NowUnixTime()
        {
            return new DateTimeOffset(DateTime.Now).ToUnixTimeMilliseconds();
        }

        public void Start()
        {
            StartTime = NowUnixTime();
        }

        public long Elapsed
        {
            get { return NowUnixTime() - StartTime; }
        }
    }

    public class TimerStat
    {
        List<long> sum = new List<long>();
        List<long> start = new List<long>();

        public void Start(int i)
        {
            if (SL.MEASURE_TIME)
            {
                while (sum.Count() <= i)
                {
                    sum.Add(0L);
                    start.Add(0L);
                }

                start[i] = Timer.NowUnixTime();
            }
        }

        public void Stop(int i)
        {
            if (SL.MEASURE_TIME)
            {
                sum[i] += Timer.NowUnixTime() - start[i];
            }
        }

        public void Print()
        {
            if (SL.MEASURE_TIME && sum.Count > 0)
            {
                var sb = new StringBuilder();
                sb.Append("[");
                for (int i = 0; i < sum.Count; i++)
                {
                    sb.Append(sum[i]);
                    sb.Append(", ");
                }

                sb.Append("]");
                Console.Error.WriteLine(sb.ToString());
            }
        }
    }

    public class BitSet
    {
        public long[] bits;
        public int n;

        public BitSet(int n)
        {
            this.n = n;
            bits = new long[(n - 1) / 64 + 1];
        }

        public int NextSetBit(int st)
        {
            for (int i = st; i < n; i++)
            {
                if (Get(i)) return i;
            }

            return -1;
        }

        public bool Get(int i)
        {
            int a = i / 64;
            int b = i % 64;
            return ((bits[a] >> b) & 1L) == 1L;
        }

        public void Set(int i)
        {
            int a = i / 64;
            int b = i % 64;
            bits[a] |= (1L << b);
        }

        public void Clear(int i)
        {
            int a = i / 64;
            int b = i % 64;
            bits[a] &= ~(1L << b);
        }
    }
}

Submission Info

Submission Time
Task B - Food Collector
User threecourse
Language C# (Mono-mcs 6.8.0.105)
Score 15216
Code Size 12130 Byte
Status
Exec Time 581 ms
Memory 43712 KB

Judge Result

Set Name Score / Max Score Test Cases
test_01 1607 / 20000 subtask_01_01.txt
test_02 1840 / 20000 subtask_01_02.txt
test_03 1527 / 20000 subtask_01_03.txt
test_04 970 / 20000 subtask_01_04.txt
test_05 1704 / 20000 subtask_01_05.txt
test_06 1810 / 20000 subtask_01_06.txt
test_07 1618 / 20000 subtask_01_07.txt
test_08 1338 / 20000 subtask_01_08.txt
test_09 1098 / 20000 subtask_01_09.txt
test_10 1704 / 20000 subtask_01_10.txt
Case Name Status Exec Time Memory
subtask_01_01.txt 390 ms 43428 KB
subtask_01_02.txt 581 ms 43616 KB
subtask_01_03.txt 428 ms 43292 KB
subtask_01_04.txt 225 ms 37300 KB
subtask_01_05.txt 391 ms 43448 KB
subtask_01_06.txt 499 ms 43284 KB
subtask_01_07.txt 446 ms 43712 KB
subtask_01_08.txt 329 ms 43316 KB
subtask_01_09.txt 241 ms 37852 KB
subtask_01_10.txt 473 ms 43548 KB