AtCoder ABC 132 C - Divide the Problems

問題

C - Divide the Problems

考え方

真っ先に全探索しようと思ったが、N, dともに最大が1oの5乗となると二重ループではLTEになってしまう。
何か上手い方法があるはずだ。

入力例をソートしてから具体例を考えていく。
[]の中の|は単純に半分にしたときの境目を表す。

• 入力例1

[1 4 4 | 6 7 9]
4と6の間で綺麗に分けられる。

• 入力例2

[1 4 4 5 | 5 9 14 14]
これだと5以上・未満で分けたとしても、3問と5問になってしまって不適。
真ん中で分けたときに左側と右側の数字が同じだと不適になりそう。
（Nは偶数という条件が加えられているのはこのためか）

次は、そのような整数の選び方が何通りあるかを、入力例1に戻って考える。

• 入力例1

[1 4 4 | 6 7 9]
「難易度4以上はARC」とすると不適。
「5以上」のときは適する。
「6以上」でも適する。
ということは、「真ん中で分けたときの右側-左側」で整数Kの選び方の数を出せる。
これを式で表すとd[N / 2] - d[n / 2 - 1]になる。
不適のとき、つまり入力例2のように真ん中で分けたとき左側と右側が同じときは、上記の式は当然0になる。
不適のときは0を出力すればよいので、結局、上記式の結果を出力すればよい。

コード

package main

import (
	"fmt"
	"sort"
)

func main() {
	var n int
	fmt.Scan(&n)
	
	d := make([]int, n)
	
	for i := range d {
		fmt.Scan(&d[i])
	}
	
	sort.Ints(d)

	fmt.Println(d[n / 2] - d[n / 2 - 1])
}