AtCoderのKeyence2019 C（Exam and Wizard）で、条件を誤解したまま実装したメモ

過去問を解いてる過程でkeyence2019_c（Exam and Wizard）を解いてみて、結局よくわからなくて解説を見たんですが、そのときはなぜその実装でいいのかがよくわかりませんでした。
https://atcoder.jp/contests/keyence2019/tasks/keyence2019_c

結果としては、
$A_1,A_2,...,A_n$と$C_1,C_2,...,C_n$の合計が同じ、という条件しか書いてないのを、
勝手に
$A_1,A_2,...,A_n$を並べ替えたものが$C_1,C_2,...,C_n$
と解釈してしまっていた（サンプルを見てそう思ってしまった）ので、前提条件を誤解していました。

ただ、その前提条件を誤解したまま実装して通ったので、自分への備忘録という意味でも残しておきます。

# 基本方針

この問題のやり方は解説PDFの通りです。
https://img.atcoder.jp/keyence2019/editorial.pdf
個人的には @drken さんのブログが大変わかりやすかったです。
https://drken1215.hatenablog.com/entry/2019/01/14/020000

ざっくりいうと$A_i \lt B_i$となっているところのマイナス分については$A_i \ge B_i$となっている項のプラスの分を使って埋めていく、という考え方です。
なので$A_i \lt B_i$となっている項の$B_i - A_i$の値の総和をSとすると、$A_i \ge B_i$となる項のそれぞれの$A_i - B_i$の値を大きい順にSから引いていって個数をカウントし、$S \leq 0$となったときの個数を$A_i \lt B_i$となっている項数に足したものが答えになります。
もともと$A_i \lt B_i$となっているところはすべて変える必要があり、それらを変えるために$A_i \ge B_i$となる項をいくつ使ったかを数えて合計している、という解釈です。

何もしなくてもすべての試験に合格できる場合(すべての$i$について $A_i \geq B_i$）や、そもそも$S \leq 0$にできない場合はうまい具合に除外するようにします。

拙いですが一応自分の実装はこちらです。
https://atcoder.jp/contests/keyence2019/submissions/12500451

# 誤解した条件を取り入れたもの

さて、自分は
$A_1,A_2,...,A_n$を並べ替えたものが$C_1,C_2,...,C_n$
という条件であると誤解していました。
なので、そういう場合では例えば以下のテストケースではうまくいきません。

```
3
2 3 100
6 7 1
```
100を6または7に当てたとしても、残りが2と3なので、どちらか片方は必ず６か７いずれかのところに置かざるを得なくなります。

もしこの条件で行うのであれば、例えば

```
3
1 5 100
2 6 1
```

みたいなケースだと、１，５の項をどうにかしなければいけないですが、５は６よりは小さくても２よりは大きいので、５を２に対して当てれば$A_i \lt B_i$となっている項の中だけで並べ替えることによって$A_i \lt B_i$となっている項を減らすことができます。
そうすることで解消できなかった項に対して$A_i \ge B_i$となっている項を使って$A_i \lt B_i$となっている項を消していく、という考え方でうまくいくはずです。
もし解消できなかった項数が$A_i \ge B_i$となっている項数よりも多い場合はNG（-1）を返す、とすればOK。
これを踏まえた上で下記のように実装しました。（これも拙い実装ですが…）
keysに$A_i \lt B_i$となっている項の$i$を持たせておいてA, Bのそれぞれの項を取ったスライスを定義して、それらを逆順に並べ替え、先頭から順に$B \leq A$となる項を探して、一致したら$A_i \lt B_i$となっている項を入れている変数の値をデクリメントする、みたいなことをしています。
そして残った項数と$A_i \ge B_i$となっている項数の比較をNGにする条件に追加しています。


```golang
package main

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

const (
	initialBufSize = 1e4
	maxBufSize     = 1e6 + 7
)

var buf []byte = make([]byte, maxBufSize)
var sc = bufio.NewScanner(os.Stdin)

func init() {
	sc.Split(bufio.ScanWords)
	sc.Buffer(buf, maxBufSize)
}

func main() {
	N := nextInt()
	An := make([]int, N)
	Bn := make([]int, N)
	var sumA, sumB, sumBAdiff, ans int
	keys := make([]int, 0)
	ABdiff := make([]int, 0)
	for i := range An {
		An[i] = nextInt()
		sumA += An[i]
	}
	for i := range Bn {
		Bn[i] = nextInt()
		sumB += Bn[i]
	}
	if sumA < sumB {
		fmt.Println(-1)
		return
	}
	for i := 0; i < N; i++ {
		if An[i] >= Bn[i] {
			ABdiff = append(ABdiff, An[i]-Bn[i])
		} else {
			sumBAdiff += Bn[i] - An[i]
			keys = append(keys, i)
			ans++
		}
	}
	if ans == 0 {
		fmt.Println(0)
		return
	}
	sort.Sort(sort.Reverse(sort.IntSlice(ABdiff)))
	minus := ans
	for i, d := range ABdiff {
		sumBAdiff -= d
		if sumBAdiff <= 0 {
			ans += i + 1
			break
		}
	}

	Amin := make([]int, len(keys))
	Bmin := make([]int, len(keys))
	for i, k := range keys {
		Amin[i] = An[k]
		Bmin[i] = Bn[k]
	}
	sort.Sort(sort.Reverse(sort.IntSlice(Amin)))
	sort.Sort(sort.Reverse(sort.IntSlice(Bmin)))
	var Amindex int
	for i := 0; i < len(Bmin); i++ {
		if Bmin[i] <= Amin[Amindex] {
			minus--
			Amindex++
		}
	}
	if sumBAdiff > 0 || minus > len(ABdiff) {
		fmt.Println(-1)
	} else {
		fmt.Println(ans)
	}
}

func nextLine() string {
	sc.Scan()
	return sc.Text()
}

func nextInt() int {
	sc.Scan()
	i, e := strconv.Atoi(sc.Text())
	if e != nil {
		panic(e)
	}
	return i
}

```

# 感想

自分の誤解から始まった検討ですが、あれこれ考えてみるのはいい勉強でした。
ただ、問題文の条件はきちんと読んで把握しましょう（戒め）