Submission #14709744


Source Code Expand

Copy
/*
https://atcoder.jp/contests/xxxx
*/

using System;
using System.Collections.Generic;
using System.Diagnostics;
using System.Linq;
using System.Text;
using System.IO;

// ReSharper disable UseObjectOrCollectionInitializer
// ReSharper disable SuggestVarOrType_BuiltInTypes
// ReSharper disable RedundantUsingDirective
// ReSharper disable CheckNamespace
// ReSharper disable PossibleNullReferenceException
// ReSharper disable AssignNullToNotNullAttribute
// ReSharper disable MemberCanBePrivate.Global
// ReSharper disable FieldCanBeMadeReadOnly.Global
// ReSharper disable FieldCanBeMadeReadOnly.Local
// ReSharper disable PrivateFieldCanBeConvertedToLocalVariable
// ReSharper disable ArrangeTypeMemberModifiers
// ReSharper disable InconsistentNaming
// ReSharper disable MemberCanBePrivate.Global


namespace Marathon
{
    // ReSharper disable once ClassNeverInstantiated.Global
    public class Program
    {
        public static void Main(string[] args)
        {
            var runner = new Runner();
            runner.Run(args);
        }
    }

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

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

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

        // ユーティリティ
        public char[] DChars = new char[] {'D', 'R', 'U', 'L'};
        public int[] DX = new int[] {0, 1, 0, -1};
        public int[] DY = new int[] {1, 0, -1, 0};

        // 入力パラメータ
        public int H, W, K, sr, sc;
        public char[,] M;
        public int N;
        public int[] FR, FC, FN, DN;

        // immutableな状態        
        public static ZobristHash zh;
        public static Board board;
        public static Dictionary<Pos, Food> foodPlace;
        public static List<Food> foodList;
        
        // mutableな状態
        public SearchState BestSearchState;

        // パラメータ
        public int Seed;

        public 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
            // 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]);
                }
            }

            // Run
            logger = new Logger(DEBUG);
            var ret = Solve();

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

            timerStat.Print();
        }

        List<char> Solve()
        {
            // 初期設定
            zh = new ZobristHash();
            board = new Board(M);
            foodList = new List<Food>();
            foodPlace = new Dictionary<Pos, Food>();
            for (int i = 0; i < N; i++)
            {
                var pos = new Pos(FR[i], FC[i]);
                var food = new Food(pos, FN[i], DN[i], i);
                foodPlace.Add(pos, food);
                foodList.Add(food);
            }
            
            // 初期状態
            var initialState = State.InitialState(sr, sc);
            var initSearchState = new SearchState();
            initSearchState.state = initialState;;
            initSearchState.evalScore = 0;
            BestSearchState = initSearchState;
            
            const int beamDepth = 2500;
            const int beamWidth = 20;
            var beams = new PriorityQueue<SearchState>[beamDepth + 1];
            Comparison<SearchState> comparison = SearchState.Comparison;
            for (int b = 0; b < beamDepth + 1; b++)
            {
                beams[b] = new PriorityQueue<SearchState>(comparison);
            }
            HashSet<int> history = new HashSet<int>();
            beams[0].Push(initSearchState);
            int chokudaiSearchIter = 0;

            while (!(timer.Elapsed > TL))
            {
                chokudaiSearchIter++;
                for (int t = 0; t < K; t++)
                {
                    logger.Debug($"ci:{chokudaiSearchIter}, t:{t}");
                    
                    int currDepth = t;
                    int nextDepth = (t + 1);

                    // 時間計測
                    if (t % 8 == 0 && timer.Elapsed > TL)
                    {
                        break;
                    }
                        
                    // ビーム幅分の状態から次の時間の状態を作成する
                    for (int iter = 0; iter < beamWidth; iter++)
                    {
                        if (beams[currDepth].Count() == 0) break;
                        SearchState currSearchState = beams[currDepth].Pop();
                        SimulateDogMove(currSearchState.state, beams[nextDepth], history, t);
                    }

                    // ビーム幅の上限を超えるcurrentDepthのビームを削除する
                    // TODO: メモリの要請がない限り必ずしも消す必要はない
                    if (beams[t].Count() > beamWidth)
                    {
                        var remainBeam = new PriorityQueue<SearchState>(comparison);
                        for (int iter = 0; iter < beamWidth; iter++)
                        {
                            remainBeam.Push(beams[currDepth].Pop());
                        }

                        beams[currDepth] = remainBeam;
                    }
                }

            }

            logger.Info($"bestScore: {BestSearchState.state.score} elapsed:{timer.Elapsed} chokudaiIter:{chokudaiSearchIter}");
            var commands = BestSearchState.state.commands;
            while (commands.Count < K)
            {
                commands.Add('-');
            }

            return commands;
        }

        double EvalScore(State state, int t)
        {
            double score = 0;

            // 現状のスコア
            score += state.score;
            score *= 1e10;

            // 残っている食物のスコアの評価
            int py = state.dog.y;
            int px = state.dog.x;
            double dist = 0;
            for (int f = 0; f < state.foodReached.Length; f++)
            {
                bool reached = state.foodReached[f];
                if (reached)
                    continue;
                var food = foodList[f];
                int y = food.pos.y;
                int x = food.pos.x;
                int tmp_score = food.score - t * food.dec;
                if (tmp_score < 0)
                {
                    dist -= Math.Abs(py - y) + Math.Abs(px - x);
                }
                else
                {
                    // TODO: 理由不明
                    dist += Math.Log10(tmp_score) * (Math.Abs(py - y) + Math.Abs(px - x));
                }
            }

            score -= dist;
            return score;
        }

        void SimulateDogMove(State currentState, PriorityQueue<SearchState> beam, HashSet<int> history, int time)
        {
            for (int d = 0; d < DChars.Length; d++)
            {
                Pos curr_dog = currentState.dog;
                int py = curr_dog.y;
                int px = curr_dog.x;
                int ny = py + DY[d];
                int nx = px + DX[d];
                
                if (!board.IsValid(ny, nx))
                    continue;
                var st = currentState.Copy();

                logger.Debug($"time:{time} - [{py}, {px}] -> [{ny}, {nx}]");
                
                // position
                st.dog = new Pos(ny, nx);
                st.hash ^= zh.hashDog[py, px];
                st.hash ^= zh.hashDog[ny, nx];
                
                // food
                if (Runner.foodPlace.ContainsKey(st.dog))
                {
                    var food = Runner.foodPlace[st.dog];
                    if (!st.foodReached[food.index])
                    {
                        int foodScore = food.score - time * food.dec;
                        st.foodReached[food.index] = true;
                        st.score += foodScore;
                        st.hash ^= zh.hashFood[time, st.dog.y, st.dog.x];
                    }
                }
                
                // time
                st.hash ^= zh.hashTime[time];
                st.hash ^= zh.hashTime[time + 1];

                // command
                st.commands.Add(DChars[d]);
                
                // history
                if (history.Contains(st.hash))
                    continue;
                history.Add(st.hash);
                
                // nextState
                var nextSearch = new SearchState();
                nextSearch.state = st;
                nextSearch.evalScore = EvalScore(st, time);
                
                if (time + 1 < K)
                {
                    beam.Push(nextSearch);
                    
                    // どのtimestepであっても、RealizedScoreが最も高いStateを保持する
                    if (nextSearch.RealizedScore > BestSearchState.RealizedScore)
                        BestSearchState = nextSearch;
                }
            }
        }

    }

    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();
        }
    }

    #region Data

    public class SearchState
    {
        public State state;
        public double evalScore;
        public double RealizedScore => state.score;

        // スコアが高い方が比較上小さくなる
        public static Comparison<SearchState> Comparison
            = (SearchState s1, SearchState s2) => s1.evalScore.CompareTo(s2.evalScore) * (-1);
    }

    public class Board
    {
        public char[,] board;

        public int H => board.GetLength(0);
        public int W => board.GetLength(1);

        public Board(char[,] board)
        {
            this.board = board;
        }

        public bool IsValid(int y, int x)
        {
            if (y < 0 || y >= H) return false;
            if (x < 0 || x >= W) return false;
            if (board[y, x] == '#') return false;
            return true;
        }
    }

    public class Food
    {
        public Pos pos;
        public int score;
        public int dec;
        public int index;

        public Food(Pos pos, int score, int dec, int index)
        {
            this.pos = pos;
            this.score = score;
            this.dec = dec;
            this.index = index;
        }
    }

    public class State
    {
        public Pos dog;
        public bool[] foodReached;
        public int score;
        public int hash; // ハッシュ
        public List<char> commands;

        public static State InitialState(int y, int x)
        {
            var ret = new State();
            ret.dog = new Pos(y, x);
            ret.foodReached = new bool[Runner.foodList.Count];
            ret.score = 0;
            ret.hash = ret.CalcHash(0, Runner.zh);
            ret.commands = new List<char>();
            return ret;
        }
        public State Copy()
        {
            var ret = new State();
            ret.foodReached = foodReached.ToArray();
            ret.dog = dog;
            ret.score = score;
            ret.commands = commands.ToList();
            ret.hash = hash;
            return ret;
        }
        
        public int CalcHash(int time, ZobristHash zh)
        {
            int key = 0;
            key ^= zh.hashTime[time];
            for (int f = 0; f < foodReached.Length; f++)
            {
                if (foodReached[f])
                    continue;
                var food = Runner.foodList[f];
                int py = food.pos.y;
                int px = food.pos.x;
                key ^= zh.hashFood[time, py, px];
            }

            {
                int py = dog.y;
                int px = dog.x;
                key ^= zh.hashDog[py, px];
            }
            return key;
        }
    }

    #endregion

    #region Structure

    public struct Pos
    {
        public int y;
        public int x;

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

    public class PriorityQueue<T>
    {
        private Comparison<T> _comparison;
        private int _type = 0;

        private T[] _heap;
        private int _sz = 0;

        private int _count = 0;

        /// <summary>
        /// Priority Queue with custom comparer
        /// </summary>
        public PriorityQueue(Comparison<T> comparison)
        {
            _heap = new T[128];
            _comparison = comparison;
        }

        private int Compare(T x, T y)
        {
            return _comparison(x, y);
        }

        public void Push(T x)
        {
            _count++;
            if (_count > _heap.Length)
            {
                var newheap = new T[_heap.Length * 2];
                for (int n = 0; n < _heap.Length; n++) newheap[n] = _heap[n];
                _heap = newheap;
            }

            //node number
            var i = _sz++;

            while (i > 0)
            {
                //parent node number
                var p = (i - 1) / 2;

                if (Compare(_heap[p], x) <= 0) break;

                _heap[i] = _heap[p];
                i = p;
            }

            _heap[i] = x;
        }

        public T Pop()
        {
            _count--;

            T ret = _heap[0];
            T x = _heap[--_sz];

            int i = 0;
            while (i * 2 + 1 < _sz)
            {
                //children
                int a = i * 2 + 1;
                int b = i * 2 + 2;

                if (b < _sz && Compare(_heap[b], _heap[a]) < 0) a = b;

                if (Compare(_heap[a], x) >= 0) break;

                _heap[i] = _heap[a];
                i = a;
            }

            _heap[i] = x;

            return ret;
        }

        public int Count()
        {
            return _count;
        }

        public T Peek()
        {
            return _heap[0];
        }

        public bool Contains(T x)
        {
            for (int i = 0; i < _sz; i++)
                if (x.Equals(_heap[i]))
                    return true;
            return false;
        }

        public void Clear()
        {
            while (this.Count() > 0) this.Pop();
        }

        public IEnumerator<T> GetEnumerator()
        {
            var ret = new List<T>();

            while (this.Count() > 0)
            {
                ret.Add(this.Pop());
            }

            foreach (var r in ret)
            {
                this.Push(r);
                yield return r;
            }
        }

        public T[] ToArray()
        {
            T[] array = new T[_sz];
            int i = 0;

            foreach (var r in this)
            {
                array[i++] = r;
            }

            return array;
        }
    }

    #endregion

    #region Specific

    public class ZobristHash
    {
        const int MAX_HW = 50;
        const int MAX_TIME = 2510;
        Random rand = new Random(71);

        public int[,] hashDog;
        public int[] hashTime;
        public int[,,] hashFood;

        public ZobristHash()
        {
            hashDog = new int[MAX_HW, MAX_HW];
            hashTime = new int[MAX_TIME];
            hashFood = new int[MAX_TIME, MAX_HW, MAX_HW];

            for (int i = 0; i < MAX_HW; i++)
            {
                for (int j = 0; j < MAX_HW; j++)
                {
                    hashDog[i, j] = rand.Next();
                }
            }

            for (int i = 0; i < MAX_TIME; i++)
            {
                hashTime[i] = rand.Next();
            }

            for (int i = 0; i < MAX_TIME; i++)
            {
                for (int j = 0; j < MAX_HW; j++)
                {
                    for (int k = 0; k < MAX_HW; k++)
                    {
                        hashFood[i, j, k] = rand.Next();
                    }
                }
            }
        }
    };

    #endregion

    #region 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 (Runner.MEASURE_TIME)
            {
                while (sum.Count() <= i)
                {
                    sum.Add(0L);
                    start.Add(0L);
                }

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

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

        public void Print()
        {
            if (Runner.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());
            }
        }
    }

    #endregion
}

Submission Info

Submission Time
Task B - Food Collector
User threecourse
Language C# (Mono-mcs 6.8.0.105)
Score 19511
Code Size 21586 Byte
Status
Exec Time 9138 ms
Memory 784208 KB

Judge Result

Set Name Score / Max Score Test Cases
test_01 1847 / 20000 subtask_01_01.txt
test_02 2646 / 20000 subtask_01_02.txt
test_03 2016 / 20000 subtask_01_03.txt
test_04 1128 / 20000 subtask_01_04.txt
test_05 2017 / 20000 subtask_01_05.txt
test_06 2545 / 20000 subtask_01_06.txt
test_07 2118 / 20000 subtask_01_07.txt
test_08 1689 / 20000 subtask_01_08.txt
test_09 1184 / 20000 subtask_01_09.txt
test_10 2321 / 20000 subtask_01_10.txt
Case Name Status Exec Time Memory
subtask_01_01.txt 9130 ms 732332 KB
subtask_01_02.txt 9125 ms 770816 KB
subtask_01_03.txt 9121 ms 723744 KB
subtask_01_04.txt 9106 ms 747904 KB
subtask_01_05.txt 9127 ms 735796 KB
subtask_01_06.txt 9138 ms 784208 KB
subtask_01_07.txt 9119 ms 704576 KB
subtask_01_08.txt 9120 ms 706780 KB
subtask_01_09.txt 9102 ms 675908 KB
subtask_01_10.txt 9119 ms 754280 KB