#783371 (C#) No.5007 Steiner Space Travel

提出ソース

結果

問題	No.5007 Steiner Space Travel
ユーザー	inani_waon
提出日時	2022-07-30 17:51:20
言語	C# (.NET 8.0.203)
結果	AC
実行時間	999 ms / 1,000 ms
コード長	13,023 bytes
コンパイル時間	6,817 ms
実行使用メモリ	196,036 KB
スコア	8,334,121
最終ジャッジ日時	2022-07-30 17:51:59
合計ジャッジ時間	38,104 ms
ジャッジサーバーID （参考情報）	judge13 / judge16
	純コード判定しない問題か言語

このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	984 ms 55,512 KB
testcase_01	AC	986 ms 55,388 KB
testcase_02	AC	988 ms 55,312 KB
testcase_03	AC	985 ms 55,280 KB
testcase_04	AC	985 ms 55,356 KB
testcase_05	AC	983 ms 55,320 KB
testcase_06	AC	986 ms 55,368 KB
testcase_07	AC	989 ms 57,088 KB
testcase_08	AC	983 ms 55,520 KB
testcase_09	AC	984 ms 57,716 KB
testcase_10	AC	987 ms 55,408 KB
testcase_11	AC	999 ms 59,764 KB
testcase_12	AC	985 ms 59,432 KB
testcase_13	AC	986 ms 57,196 KB
testcase_14	AC	985 ms 57,496 KB
testcase_15	AC	988 ms 57,496 KB
testcase_16	AC	986 ms 57,660 KB
testcase_17	AC	984 ms 57,196 KB
testcase_18	AC	989 ms 59,252 KB
testcase_19	AC	984 ms 57,508 KB
testcase_20	AC	986 ms 57,628 KB
testcase_21	AC	984 ms 57,356 KB
testcase_22	AC	985 ms 59,224 KB
testcase_23	AC	985 ms 57,420 KB
testcase_24	AC	984 ms 57,676 KB
testcase_25	AC	985 ms 57,360 KB
testcase_26	AC	986 ms 59,484 KB
testcase_27	AC	986 ms 57,236 KB
testcase_28	AC	988 ms 57,068 KB
testcase_29	AC	984 ms 196,036 KB

権限があれば一括ダウンロードができます

コンパイルメッセージ

  Determining projects to restore...
  Restored /home/judge/data/code/main.csproj (in 110 ms).
.NET 向け Microsoft (R) Build Engine バージョン 17.0.0-preview-21470-01+cb055d28f
Copyright (C) Microsoft Corporation.All rights reserved.

  プレビュー版の .NET を使用しています。https://aka.ms/dotnet-core-preview をご覧ください
  main -> /home/judge/data/code/bin/Release/net6.0/main.dll
  main -> /home/judge/data/code/bin/Release/net6.0/publish/

ソースコード

raw source code

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

class Yukico5007
{
    static void Main(string[] args)
    {
        var sw = Stopwatch.StartNew();
        var nums = Console.ReadLine().Split(' ').Select(int.Parse).ToArray();
        var N = nums[0];
        var M = nums[1];

        var planets = new List<(int y, int x)>();
        for (int i = 0; i < N; i++)
        {
            nums = Console.ReadLine().Split(' ').Select(int.Parse).ToArray();
            planets.Add((nums[0], nums[1]));
        }

        var directCosts = new double[(N + 1) * (N + 1)];
        for (int i = 0; i < N; i++)
        {
            for (int j = 0; j < N; j++)
            {
                if (i == j) continue;
                var cost = Math.Sqrt(Math.Abs(planets[i].y - planets[j].y) * Math.Abs(planets[i].y - planets[j].y) +
                                     Math.Abs(planets[i].x - planets[j].x) * Math.Abs(planets[i].x - planets[j].x));
                directCosts[i * (N + 1) + j] = cost;
            }
        }
        for (int i = 0; i < N; i++)
        {
            directCosts[(N + 1) * N + i] = directCosts[0 * (N + 1) + i];
            directCosts[(N + 1) * i + N] = directCosts[i * (N + 1) + 0];
        }

        var inputs = new Inputs(sw, planets, directCosts, null);
        var solver = new Solver();
        var command = solver.GetCommand(inputs);
        command.Print();
    }
}

class Inputs
{
    /// <summary>惑星の座標</summary>
    public List<(int y, int x)> Planets;

    /// <summary>他の惑星を経由せずに直接飛ぶコスト(αは考慮しない)</summary>
    public double[] DirectCosts;
    /// <summary>他の惑星を経由して飛ぶ最小コスト(αは考慮しない)</summary>
    public double[] RouteCosts;

    public Stopwatch Sw;
    public const int N = 100;
    public const int NP1 = 101;
    public const int M = 8;
    public const int A = 5;
    public const int AA = 25;

    public Inputs(Stopwatch sw, List<(int y, int x)> planets, double[] directCosts, double[] routeCosts)
    {
        Sw = sw;
        Planets = planets;
        DirectCosts = directCosts;
        RouteCosts = routeCosts;
    }
}

class Outputs
{
    public List<(int y, int x)> Stations = new();
    public List<(int t, int r)> Route = new();
    public double Cost;

    public void Print()
    {
        foreach (var pos in Stations)
        {
            Console.WriteLine($"{pos.y} {pos.x}");
        }
        Console.WriteLine(Route.Count);
        foreach (var via in Route)
        {
            Console.WriteLine($"{via.t} {via.r + 1}");
        }
    }
}

class Solver
{
    public Outputs GetCommand(Inputs inputs)
    {
        var defaultRoute = Enumerable.Range(0, Inputs.N).Append(0).ToArray();
        var twoOpt = new TwoOpt(Inputs.NP1, inputs.DirectCosts, defaultRoute, new Random(1728), inputs.Sw);
        twoOpt.Exec();

        var res = new Outputs();
        foreach (var i in twoOpt.IdxByOrders)
        {
            res.Route.Add((1, i));
        }
        res = AddStations(inputs, res, twoOpt.IdxByOrders);
        res = Yaki(inputs, res, twoOpt.IdxByOrders);
        return res;
    }

    int[] GetInitRoute(Inputs inputs)
    {
        var res = new int[Inputs.NP1];
        var seen = new Span<bool>(new bool[Inputs.N]);
        seen[0] = true;
        var bf = 0;
        for (int i = 1; i < Inputs.N; i++)
        {
            var bestIdx = -1;
            var bestCost = double.MaxValue;
            for (int j = 1; j < Inputs.N; j++)
            {
                if (seen[j]) continue;
                var cost = inputs.DirectCosts[bf * Inputs.NP1 + j];
                if (cost < bestCost)
                {
                    bestIdx = j;
                    bestCost = cost;
                }
            }
            res[i] = bestIdx;
            bf = bestIdx;
            seen[bestIdx] = true;
        }
        return res;
    }

    Outputs AddStations(Inputs inputs, Outputs outputs, int[] order)
    {
        while (outputs.Stations.Count < 8)
        {
            var maxCost = double.MinValue;
            var maxCostIndex = -1;  // (i - 1) -> i

            for (int i = 1; i < outputs.Route.Count; i++)
            {
                var bf = outputs.Route[i - 1];
                var af = outputs.Route[i];
                if (af.t == 2 || af.t == 2) continue;
                double cost;
                if (bf.t == 1 && af.t == 1)
                {
                    cost = inputs.DirectCosts[bf.r * Inputs.NP1 + af.r] * Inputs.AA;
                }
                else
                {
                    var rate = (bf.t == 2 && af.t == 2) ? 1 : Inputs.A;
                    var bfPos = bf.t == 1 ? inputs.Planets[bf.r] : outputs.Stations[bf.r];
                    var afPos = af.t == 1 ? inputs.Planets[af.r] : outputs.Stations[af.r];
                    cost = Math.Sqrt(Math.Abs(bfPos.y - afPos.y) * Math.Abs(bfPos.y - afPos.y) +
                                     Math.Abs(bfPos.x - afPos.x) * Math.Abs(bfPos.x - afPos.x)) * rate;
                }
                if (cost > maxCost)
                {
                    maxCostIndex = i;
                    maxCost = cost;
                }
            }

            var bf2 = outputs.Route[maxCostIndex - 1];
            var af2 = outputs.Route[maxCostIndex];
            var bfPos2 = bf2.t == 1 ? inputs.Planets[bf2.r] : outputs.Stations[bf2.r];
            var afPos2 = af2.t == 1 ? inputs.Planets[af2.r] : outputs.Stations[af2.r];
            var y = (bfPos2.y + afPos2.y) / 2;
            var x = (bfPos2.x + afPos2.x) / 2;

            outputs.Stations.Add((y, x));
            outputs = GetNextRoute(inputs, outputs, order);
        }
        return outputs;
    }

    Outputs GetNextRoute(Inputs inputs, Outputs outputs, int[] order)
    {
        var res = new Outputs();
        res.Stations = new List<(int y, int x)>(outputs.Stations);
        res.Route.Add((1, 0));
        for (int i = 1; i < order.Length; i++)
        {
            var bfPlanet = order[i - 1];
            var directCost = inputs.DirectCosts[bfPlanet * Inputs.NP1 + order[i]] * inputs.DirectCosts[bfPlanet * Inputs.NP1 + order[i]] * Inputs.AA;   // 直接

            var bestT = 1;
            var bestR = -1;
            var bestCost = directCost;

            var bfPos = inputs.Planets[bfPlanet];
            var afPos = inputs.Planets[order[i]];
            for (int j = 0; j < res.Stations.Count; j++)
            {
                var ctPos = res.Stations[j];
                var cost1 = Math.Sqrt(Math.Abs(bfPos.y - ctPos.y) * Math.Abs(bfPos.y - ctPos.y) +
                                      Math.Abs(bfPos.x - ctPos.x) * Math.Abs(bfPos.x - ctPos.x));
                var cost2 = Math.Sqrt(Math.Abs(afPos.y - ctPos.y) * Math.Abs(afPos.y - ctPos.y) +
                                      Math.Abs(afPos.x - ctPos.x) * Math.Abs(afPos.x - ctPos.x));
                cost1 = cost1 * cost1 * Inputs.A;
                cost2 = cost2 * cost2 * Inputs.A;
                if (cost1 + cost2 < bestCost)
                {
                    bestT = 2;
                    bestR = j;
                    bestCost = cost1 + cost2;
                }
            }
            
            if (bestR != -1)
            {
                res.Route.Add((bestT, bestR));
            }
            res.Route.Add((1, order[i]));
            res.Cost += bestCost;
        }
        return res;
    }

    Outputs GetNextRoute(Inputs inputs, Outputs outputs, List<(int y, int x)> stations, int[] order, double[] costs)
    {
        var res = new Outputs();
        res.Stations = new List<(int y, int x)>(stations);
        res.Route.Add((1, 0));
        for (int i = 1; i < order.Length; i++)
        {
            var bfPlanet = order[i - 1];
            var directCost = inputs.DirectCosts[bfPlanet * Inputs.NP1 + order[i]] * inputs.DirectCosts[bfPlanet * Inputs.NP1 + order[i]] * Inputs.AA;   // 直接

            var bestT = 1;
            var bestR = -1;
            var bestCost = directCost;

            for (int j = 0; j < stations.Count; j++)
            {
                var cost1 = costs[j * Inputs.NP1 + bfPlanet];
                var cost2 = costs[j * Inputs.NP1 + order[i]];
                if (cost1 + cost2 < bestCost)
                {
                    bestT = 2;
                    bestR = j;
                    bestCost = cost1 + cost2;
                }
            }

            if (bestR != -1)
            {
                res.Route.Add((bestT, bestR));
            }
            res.Route.Add((1, order[i]));
            res.Cost += bestCost;
        }
        return res;
    }

    Outputs Yaki(Inputs inputs, Outputs outputs, int[] order)
    {
        var best = outputs;
        var random = new Random(1728);

        // 惑星とstationとの距離を前計算
        var costs = new double[best.Stations.Count * order.Length];
        for (int st = 0; st < best.Stations.Count; st++)
        {
            for (int pl = 0; pl < Inputs.N; pl++)
            {
                var bfPos = inputs.Planets[pl];
                var ctPos = best.Stations[st];
                var cost = Math.Sqrt(Math.Abs(bfPos.y - ctPos.y) * Math.Abs(bfPos.y - ctPos.y) +
                                          Math.Abs(bfPos.x - ctPos.x) * Math.Abs(bfPos.x - ctPos.x));
                costs[st * Inputs.NP1 + pl] = cost * cost * Inputs.A;
            }
        }

        while (inputs.Sw.ElapsedMilliseconds < 950)
        {
            var width = 40 - (int)((inputs.Sw.ElapsedMilliseconds - 300) / 200);
            var stations = new List<(int y, int x)>(best.Stations);
            var idx = random.Next(0, stations.Count);
            var y = Math.Max(0, Math.Min(1000, stations[idx].y + random.Next(width * 2 + 1) - width));
            var x = Math.Max(0, Math.Min(1000, stations[idx].x + random.Next(width * 2 + 1) - width));
            stations[idx] = (y, x);

            var workCosts = new double[costs.Length];
            Array.Copy(costs, workCosts, costs.Length);
            for (int pl = 0; pl < Inputs.N; pl++)
            {
                var bfPos = inputs.Planets[pl];
                var ctPos = stations[idx];
                var cost = Math.Sqrt(Math.Abs(bfPos.y - ctPos.y) * Math.Abs(bfPos.y - ctPos.y) +
                                     Math.Abs(bfPos.x - ctPos.x) * Math.Abs(bfPos.x - ctPos.x));
                workCosts[idx * Inputs.NP1 + pl] = cost * cost * Inputs.A;
            }

            var work = GetNextRoute(inputs, outputs, stations, order, workCosts);
            if (work.Cost < best.Cost)
            {
                best = work;
                Array.Copy(workCosts, costs, costs.Length);
            }            
        }
        return best;
    }
}

public class TwoOpt
{
    public readonly int NodeCount;
    public readonly int NodeCount2;
    public readonly double[] Costs;
    /// <summary>idx番目に経由する点がvalue番目の要素</summary>
    public readonly int[] IdxByOrders;

    Random _random;
    System.Diagnostics.Stopwatch _sw;

    public TwoOpt(int n, double[] costs, int[] defaultOrder, Random random, System.Diagnostics.Stopwatch sw)
    {
        NodeCount = n;
        NodeCount2 = defaultOrder.Length;
        Costs = costs;
        IdxByOrders = new int[NodeCount2];
        Array.Copy(defaultOrder, IdxByOrders, NodeCount2);
        _random = random;
        _sw = sw;
    }

    public void Exec()
    {
        //var cnt = 0;
        var costsSpan = new Span<double>(Costs);
        while (_sw.ElapsedMilliseconds < 300)
        {
            for (int i = 0; i < 100; i++)
            {
                // 先頭、末尾は交換しない
                var from1order = _random.Next(NodeCount2 - 4);
                var from2order = _random.Next(from1order + 3, NodeCount2);

                var from1 = IdxByOrders[from1order];
                var from2 = IdxByOrders[from2order];
                var to1 = IdxByOrders[from1order + 1];
                var to2 = IdxByOrders[from2order - 1];

                // コスト計算
                var oldRouteCost = costsSpan[from1 * NodeCount + to1] + costsSpan[from2 * NodeCount + to2];
                var newRouteCost = costsSpan[from1 * NodeCount + to2] + costsSpan[from2 * NodeCount + to1];

                // 改善されていれば更新
                if (newRouteCost < oldRouteCost)
                {
                    //Debug.WriteLine(_sw.ElapsedMilliseconds);
                    Swap(from1order, from2order);
                }
            }
            //cnt++;
        }
    }

    /// <summary>
    /// 2点の接続を交換する
    /// </summary>
    /// <param name="from1order">点1のOrder順</param>
    /// <param name="from2order">点2のOrder順</param>
    public void Swap(int from1order, int from2order)
    {
        Array.Reverse(IdxByOrders, from1order + 1, from2order - from1order - 1);
    }
}

yukicoder

結果

テストケース

コンパイルメッセージ

ソースコード