Go言語で挑む競プロ #6
前回はこちらから。
前回から一週間と少し空いてしまったけど、今回も解いていこうと思う。
今回は、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)
}
今回は、とてもシンプルなアルゴリズムで実装しやすかった。
スラスラっとアルゴリズムも思いついたし、いい感じ。
ほかの問題もこれぐらい、さらっと解いていきたいなぁ。
さぁ、次回も頑張ろ。
この記事が気に入ったらサポートをしてみませんか?