前回はこちらから。

前回から一週間と少し空いてしまったけど、今回も解いていこうと思う。
今回は、ABC115Cを解いていこう。

ABC115Cの問題

問題文
とある世界では、今日はクリスマスイブです。
高羽氏の庭には N 本の木が植えられています。
i 本目の木 (1≤i≤N) の高さは hi メートルです。
彼は、これらの木のうち K 本を選んで電飾を施すことにしました。
より美しい光景をつくるために、できるだけ近い高さの木を飾り付けたいです。
より具体的には、飾り付ける木のうち最も高いものの高さを hmax メートル、最も低いものの高さを hmin メートルとすると、hmax−hmin が小さいほど好ましいです。
hmax−hmin は最小でいくつにすることができるでしょうか？

制約
- 2≤K<N≤10^5
- 1≤hi≤10^9
- hi は整数である。

今回は簡単そうかな。

アルゴリズム

シンプルにこんな感じのアルゴリズムに。

1. 全ての木の高さを受け取る
2. 木の高さをソートする
3. そこからk個連続した区間を全て抽出
4. 抽出した区間の最高と最低の高さの差を計算
5. 最小の差を解答する

ソート後のk個の連続した区間は、以下のパターンが存在する。

最低の高さの木 ~ 最高の高さの木
1 ~ (n - k)
2 ~ (n - k + 1)
         :
(n - k - 1) ~ (n - 1)
(n - k) ~ n

このパターンを全部探索して、高さの差の最小を求めるには、以下のようなループを書けばよいかな。

ans := 9999999999
for i := 0; i <= n-k; i++ {
    if d := hl[i+k-1] - hl[i]; d < ans {
        ans = d
    }
}

あとは、入力と出力の処理などを追加して完成だ～。

解答

最終的には以下のようなコードに。

package main

import (
    "bufio"
    "fmt"
    "os"
    "sort"
    "strconv"
)

func main() {
    sc := bufio.NewScanner(os.Stdin)
    sc.Split(bufio.ScanWords)
    sc.Scan()
    n, _ := strconv.Atoi(sc.Text())
    sc.Scan()
    k, _ := strconv.Atoi(sc.Text())

    hl := make([]int, n)
    for i := 0; i < n; i++ {
	sc.Scan()
	h, _ := strconv.Atoi(sc.Text())
	hl[i] = h
    }

    sort.Ints(hl)

    ans := 9999999999
    for i := 0; i <= n-k; i++ {
        if d := hl[i+k-1] - hl[i]; d < ans {
	    ans = d
	}
    }

    fmt.Println(ans)
}

今回は、とてもシンプルなアルゴリズムで実装しやすかった。
スラスラっとアルゴリズムも思いついたし、いい感じ。
ほかの問題もこれぐらい、さらっと解いていきたいなぁ。

さぁ、次回も頑張ろ。