結果

問題 No.5007 Steiner Space Travel
コンテスト
ユーザー inani_waon
提出日時 2022-07-30 15:00:42
言語 C#
(.NET 8.0.404)
結果
AC  
実行時間 997 ms / 1,000 ms
コード長 5,055 bytes
コンパイル時間 7,092 ms
実行使用メモリ 166,744 KB
スコア 5,933,451
最終ジャッジ日時 2022-07-30 15:01:28
合計ジャッジ時間 39,633 ms
ジャッジサーバーID
（参考情報） 		judge13 / judge14
純コード判定しない問題か言語
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 30
権限があれば一括ダウンロードができます
コンパイルメッセージ
  Determining projects to restore...
  Restored /home/judge/data/code/main.csproj (in 117 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/

ソースコード

diff # 

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, directCosts, null);
        var solver = new Solver();
        var command = solver.GetCommand(inputs);
        command.Print();
    }
}

class Inputs
{
    /// <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 Inputs(Stopwatch sw, double[] directCosts, double[] routeCosts)
    {
        Sw = sw;
        DirectCosts = directCosts;
        RouteCosts = routeCosts;
    }
}

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

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

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();
        for (int i = 0; i < Inputs.M; i++)
        {
            res.Stations.Add((0, 0));
        }
        foreach (var i in twoOpt.IdxByOrders)
        {
            res.Route.Add((1, i + 1));
        }
        return res;
    }
}

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 < 950)
        {
            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) 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);
    }
}
0