はじめに

競技プログラミング、AtCoder Beginner Contest 107
C - Candles
言語はC#
何かあればTwitter→@pirorirori_n712まで

問題

問題文

数直線上にN本のろうそくが置かれています。
左からi番目のろうそくは座標xiに置かれています。
ただし、x1<x2<...<xNが成り立ちます。
最初、どのろうそくにも火が付いていません。
すぬけ君は、N本のうちK本のろうそくに火を付けることにしました。

今、すぬけ君は座標0にいます。
すぬけ君は、数直線上を左右に速度1で移動することができます。
また、自分と同じ座標のろうそくに火を付けることができます。
このとき、火を付けるのに掛かる時間は無視できます。

K本のろうそくに火を付けるのに必要な最小の時間を求めてください

制約

・1≤N≤10^5
・1≤K≤N
・xiは整数である。
・|xi|≤10^8
・x1<x2< ... <xN

入力

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

N K
x1 x2 ... xN

出力

K本のろうそくに火を付けるのに必要な最小の時間を出力せよ

解き方

以下を参考にしています。
https://img.atcoder.jp/arc101/editorial.pdf
atcoder.jp

K本のろうそくに火をつける時間を最小にしようとすると
ろうそくの並びが連続している箇所につけることになります。

ろうそくのK個連続した並びを全て列挙すると
N-K+1通りになり全探索が使えそうなので
ループで列挙していくことにします。

ループの中の処理を考えます。

開始地点の座標は0であることが決まっているので、
Kを仮に3とし、
火をつけるろうそくを「A,B,C」とすると
ろうそくのつけ方は以下の2パターンになります。

①0→A→B→C
②0→C→B→A

ここで出したろうそくをつけるのにかかる時間を
保存しておき、
後で最小値を出せばそれが答えになります。
（もしくは常に最小値を保存）

全体のコード

using System;
using System.Collections.Generic;
using System.Linq;

class Cmondai
{
    static void Main()
    {
        var nk = Console.ReadLine().Split(' ').Select(value => Int32.Parse(value)).ToArray();
        var N = nk[0];
        var K = nk[1];
        //N個のろうそくのうち、連続したK個の組み合わせの個数
        var count = N - K + 1;
        var x = Console.ReadLine().Split(' ').Select(value => Int64.Parse(value)).ToArray();
        //かかる時間を保存
        var cost = new List<long>();
        //ろうそくK個の組み合わせの数ぶん、ループ
        for (int i = 0; i < count; ++i)
        {
            //K個のろうそくで、右端から左端までかかる時間
            var l = Math.Abs(x[i] - x[i + K - 1]);
            //0→左端…
            //左端から0までの時間を足して、リストに保存
            cost.Add(Math.Abs(x[i]) + l);
            //0→右端…
            //右端から0までの時間を足して、リストに保存
            cost.Add(Math.Abs(x[i + K - 1]) + l);
        }
        //最も時間の短いものが答え
        var ans = cost.Min();
        Console.WriteLine(ans);
    }
}