Go言語で挑む競プロ #18

久しぶりに過去問を解いていこうと思う。
過去問をnoteに書くのはいつぶりだろうなぁって思って振り返ってみたら、8月18日が最終投稿だった...もう少しで一か月たってしまう...
もっと頑張っていかないと！

ってことで、今回はABC132のC問題を解いていこうと思う。どんどん解いていないC問題を埋めていこう！

ABC132Cの問題

問題文
高橋君は、 N 個の競技プログラミング用の問題をつくりました。
それぞれの問題には 1 から N の番号がついており、問題 i の難易度は整数 di で表されます(大きいほど難しいです)。
高橋君はある整数 K を決めることで、難易度が K 以上ならば「 ARC 用の問題」難易度が K 未満ならば「 ABC 用の問題」という風に、これらの問題を二種類に分類しようとしています。
「ARC 用の問題」と「ABC 用の問題」が同じ数になるような整数 K の選び方は何通りあるでしょうか。

制約
- 2≦N≦10^5
- N は偶数である。
- 1≦di≦10^5
- 入力は全て整数である。

アルゴリズム

これは簡単に解けそうだね。アルゴリズムはこんな感じ。

1. 問題を難易度の昇順に並び替える
2. 問題をちょうど二分した後に、以下の値を取得する
　・前半部分のうち最も難しい難易度の値
　・後半部分のうち最も易しい難易度の値
3. 取得した値の差分が解答となる

とてもシンプルだね。
kの値の数は、二分した際の境界値の間に存在しうる値の数を求めればよい。そして、xからyの間に存在しうる値の数は、y-x となるため手順3で求めることができるはずだ。

例を見てみて正しさをチェックしてみよう。

難易度の数列： 1, 4, 4, 6, 7, 9
二分すると　： 1, 4, 4 ｜  6, 7, 9
可能なｋの値： 5, 6
解答　　　　： 6 - 4 = 2(個)

上の例だと、二分する際に取ることのできるkの値は5と6の二つとなる。そして、手順2で取得した値は、4と6となるので、6-4=2でkの個数と等しくなることがわかる。

あとは、これを実装したら完成だ！

解答

最終的には、以下のコードに。

package main

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

func main() {
   var n int
   s := wordScanner()
   scanInts(s, &n)

   l := make([]int, n)
   for i := 0; i < n; i++ {
       scanInts(s, &l[i])
   }

   sort.Ints(l)
   fmt.Println(l[n/2] - l[n/2-1])
}

func wordScanner() *bufio.Scanner {
   s := bufio.NewScanner(os.Stdin)
   s.Split(bufio.ScanWords)
   return s
}

func scanInts(s *bufio.Scanner, vals ...*int) {
   for i := range vals {
       s.Scan()
       n, _ := strconv.Atoi(s.Text())
       *vals[i] = n
   }
}

今回の問題はとても簡単だった。問題もアルゴリズムもシンプルでスムーズに解くことができた。

この調子でどんどん頑張っていくぞ！

＝＝＝＝＝＝＝＝

前回の競プロへの挑戦はこちらから。