Mister雑記

競プロ記事がメインになりますが、内容は気分次第です。

ARC101-C 「Candles」 (300)

Static Candles。

問題リンク

概要

 N本のロウソクが数直線上に並んでおり、左から i本目の座標は x_iである。

原点から移動を始めて N本中 K本のロウソクに火を付けるのに、必要な最小の移動距離を求めよ。

制約

  •  1 \leq K \leq N \leq 10^5
  •  -10^8 \leq x_1 \lt x_2 \lt \dots \lt x_N \leq 10^8

解説

まずわざわざロウソクをスルーする必要もないので、連続した K個のロウソクのみについて考えればいい。

で。具体的な移動方法を考えると、

  •  x_N \leq 0の場合
  •  x_1 \lt 0かつ 0 \gt x_Nの場合
  •  0 \leq x_1の場合

が主に考えられる。1つ目と3つ目は一番遠いロウソクへ真っ直ぐ行けばいいのだが、2番目は「より近い方の端点までいって反対側までバックする」みたいな移動方法になる。

まぁ実際にこれらを場合分けすればACなんだが、実のところこのような場合分けをしないでもいい。 というのも1つ目と3つ目も2つ目と同じ方法で多少無駄があるが最短経路は出るからだ。

実装例

#include <iostream>
using namespace std;
const int INF = 1 << 30;

int main() {
    int N, K;
    cin >> N >> K;

    int x[N];
    for (int i = 0; i < N; ++i) {
        cin >> x[i];
    }

    int ans = INF;
    for (int i = 0; i < N; ++i) {
        int j = i + K - 1;
        if (j > N - 1) break;

        // 最初にx_iとx_jの近い方に行く
        // その後x_iからx_jへ、あるいはx_jからx_iへ移動する
        ans = min(ans, min(abs(x[i]), abs(x[j])) + x[j] - x[i]);
    }

    cout << ans << endl;
    return 0;
}

感想

  • Static Sushiの弱体化版だなぁという印象。
  • できるだけ楽な実装をしていきたいね。