過去問を解いてる過程で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にする条件に追加しています。
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
}
感想
自分の誤解から始まった検討ですが、あれこれ考えてみるのはいい勉強でした。
ただ、問題文の条件はきちんと読んで把握しましょう（戒め）