最近新しくJavascriptをやるのにハマっています、ねむーです。

今回はAtCoder(https://atcoder.jp/contests/abc117)にて開催されました、AtCoder Beginner Contest 117の第三回目です。

今回は、第三問「C - Streamline」の問題と僕との戦闘記です。

0.はじめに

今回も、プログラミング言語はC#を使用しています。

1.問題文

数直線と N 個のコマを用いて 1 人でゲームを行います。

はじめ、これらのコマをそれぞれ好きな整数座標に置きます。

このとき、同じ座標に複数のコマを置いても構いません。

以下の移動を繰り返して、座標 X 1 , X 2 , . . . , X M の M 個の地点全てをいずれかのコマで訪れることが目的です。

移動: コマを 1 つ選び、そのコマの座標を x とする。そのコマを座標 x + 1 もしくは座標 x − 1 に移動する。

ただし、最初にコマを置いた座標はその時点で訪れたとみなします。

目的を達成するまでに移動を行う回数の最小値を求めてください。

2.入力例

入力

入力は以下の形式で標準入力から与えられる。

N M
X_1 X_2 … X_M

出力

目的を達成するまでに移動を行う回数の最小値を出力せよ。

3.初見の感想

入力の分割とパースが必要
最も効率的な置き方がわからなかった

4.学びポイント

最も効率的な置き方はターゲットどうしの距離が長い部分を移動しないような置き方！
つまり人数-1個分のターゲットどうしの距離が長い部分をカットできる

それぞれの人のカバー範囲はこのようなイメージになりますね！ f:id:nemurin_blog:20190212005537p:plain

5.コードの簡単な解説

まず、入力の値のパースを行う

            string[] temp = System.Console.ReadLine().Split(' ');
            int N = int.Parse(temp[0]);
            int M = int.Parse(temp[1]);
            string[] temp1 = System.Console.ReadLine().Split(' ');
            int[] target = new int[M];
            for (int i = 0; i < M; i++)
            {
                target[i] = int.Parse(temp[i]);
            }

目的地間で最も距離が離れている場所を探す

→目的地をソートして連続する目的地の差を調べる

            Array.Sort(target);
            int[] distance = new int[target.Length];
            for (int i = 1; i < target.Length; i++)
            {
                distance[i] = target[i]-target[i-1];
            }

人と人の間で通らない場所を除いた、和が答えとなる

            var dsDesc = E.Range(0, distance.Length).ToArray();
            Array.Sort(distance.ToArray(), dsDesc);
            Array.Reverse(dsDesc);

            var k = target.Last() - target.First() - dsDesc.Take(N - 1).Sum(x => d[x]);
            Console.WriteLine(k);

6.全コード

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
using E = System.Linq.Enumerable;
    class Program
    {
        static void Main(string[] args)
        {
            string[] temp = System.Console.ReadLine().Split(' ');
            int N = int.Parse(temp[0]);
            int M = int.Parse(temp[1]);
            string[] temp1 = System.Console.ReadLine().Split(' ');
            int[] target = new int[M];
            for (int i = 0; i < M; i++)
            {
                target[i] = int.Parse(temp1[i]);
            }
            Array.Sort(target);
            int[] distance = new int[target.Length];
            for (int i = 1; i < target.Length; i++)
            {
                distance[i] = target[i]-target[i-1];
            }
            var dsDesc = E.Range(0, distance.Length).ToArray();
            Array.Sort(distance.ToArray(), dsDesc);
            Array.Reverse(dsDesc);

            var k = target.Last() - target.First() - dsDesc.Take(N - 1).Sum(x => d[x]);
            Console.WriteLine(k);
        }
    }

7.最後に

どんどん問題がたまっていく…

どこかで決着をつけたいな…

ねむーの日記~AtCoderな日々~

福岡に住むプログラミング好きのブログです！

【プログラミングコンテスト】AtCoder Beginner Contest 117③