【競プロ】Exam and Wizardを解く

こんにちは、モリリンです。
今日も今日とて、朝から競プロ解いていきます。
今日の問題はキーエンスプログラミングコンテスト2019のC問題、Exam and Wizard です。

問題文

大学生の高橋君は $N$ 個の試験を受けてすべてに合格する必要があります．現在， $i$ 番目の試験の準備度は $A_i$ です．また，高橋君の入念な調査によって， $i$ 番目の試験に合格するためには準備度を $B_i$ 以上にしなくてはならないことが分かっています．
このままだとすべての試験に合格できないかもしれないと思った高橋君は，魔法使いの青木君に頼んで，試験の準備度の総和は変えずに，なるべく少ない数の試験の準備度を変更してもらうことで試験を乗り切ることにしました．
高橋君に代わって，以下の条件を満たす数列 $C_1,C_2,...,C_N$ を考えたときの $A_i$ と $C_i$ が異なるような $i$ の個数の最小値を求めてください．そのような数列 $C_1,C_2,...,C_N$ が構成できない場合は −1 を出力してください．

数列 $A_1,A_2,...,A_N$ の総和と数列 $C_1,C_2,...,C_N$ の総和は等しい

どの $i$ に対しても， $B_i \leq C_i$ が成り立つ

制約

1 \leq N \leq 10^5 \\ 1 \leq A_i \leq 10^9 \\ 1 \leq B_i \leq 10^9 \\

ポイント

今回の問題の場合、Nの制約が $10^5$ と少し大きいため、 $O(N)$ 、つまり、ループが一重くらいで計算できたらいいなーくらいの気持で考えます。

考えかた

まずは、入力例1をみていきます。
例1では、 ${A_i} = {2,3,5}, {B_i} = {3,4,1}$ となっています。
準備度 $A_1 < B_1$ なので、 $A_1$ を $B_1$ 以上に変更する必要があり、最低 $B_1 - A_1 = 3 - 2 = 1$ を他のところから必要になります。同じように $A_2 < B_2$ なので、 $A_2$ を $B_2$ 以上に変更するために最低 $1$ 必要になります。
なので合計 $2$ を他の準備度からもらってくる必要があります。
そして、すでに $A_3 > B_3$ となっているので、 $A_3$ を変更して、余った準備度 $A_3 - B_3 = 4$ をそれらの足りていないところに割り当てることができます。
なので、結局全ての準備度を変更する必要があるので、答えは3となります。

つまり、 $A_i < B_i$ となっている $i$ について、 $B_i - A_i$ の合計分が条件を満たすのに必要で、その分をすでに $A_i > B_i$ となっているところから $A_i$ を変更して、余った準備度 $A_i - B_i$ を割り当てればいいことになります。
そして、変更回数を最小にするために、 $A_i - B_i$ が大きなところから変更して、余った準備度を他に割り当ていきます。

そして求める答えは、
$A_i < B_i$ となっている $i$ についての、 $A_i - B_i$ の合計をreq、
$A_i > B_i$ となっている $i$ について、 $A_i - B_i$ を並べたものを extras、
その合計をs_extraとしたとき、
$req > s_extra$ なら答えは -1
それ以外の時、答えは ( $A_i < B_i$ となっている $i$ の合計) + (extrasの要素を大きい順から足していって何要素目に reqを超えるか)
になります

実装

上記のことを実装するには、まず、
req, s_extra, extras を宣言します。
なお、 resultは答えを表します。そして、 $0 \leq i < N$ について、

$A[i] > B[i]$ なら、s_extraに $A[i] - B[i]$ を足し、extrasに $A[i] - B[i]$ を追加
$A[i] < B[i]$ なら、reqに $A[i] - B[i]$ を足し、resultに１を足す

そして、extrasを降順にソートして、

extrasから要素を1つづつ取り出していって、

reqが０以下なら終了
それ以外なら、
- reqをその値で引き
- resultに１を足す

を繰り返します

Nimで書いたコードは以下になります。

import sequtils, strutils, sugar, algorithm
proc scanf(formatstr: cstring){.header: "<stdio.h>", varargs.}
proc getchar(): char {.header: "<stdio.h>", varargs.}
proc nextInt(): int = scanf("%lld", addr result)
proc nextFloat(): float = scanf("%lf", addr result)
proc nextString(): string =
  var get = false
  result = ""
  while true:
    var c = getchar()
    if int(c) > int(' '):
      get = true
      result.add(c)
    else:
      if get: break
      get = false

proc `$` [T](x: seq[T]): string = x.mapIt($it).join(" ")


proc solve(N: int, A: seq[int], B: seq[int]): int =
  var req, s_extra = 0
  var extras: seq[int]

  for i in 0..<N:
    if A[i] > B[i]:
      s_extra += A[i] - B[i]
      extras.add(A[i] - B[i])
    elif A[i] < B[i]:
      req += B[i] - A[i]
      inc(result)
  if req > s_extra:
    return -1
  extras.sort(Descending)
  for extra in extras:
    if req <= 0:
      return result
    req -= extra
    inc(result)


proc main(): void =
  var N = 0
  N = nextInt()
  var A = newSeqWith(N, 0)
  for i in 0..<N:
    A[i] = nextInt()
  var B = newSeqWith(N, 0)
  for i in 0..<N:
    B[i] = nextInt()
  echo solve(N, A, B)
  return

main()

提出結果

終わりに

いかがだったでしょうか？
今回のような問題は、実際に入力例などを手で描いてみて、自分ならどうやって解くのかを考え、それをコードに落としていく、みたいなことをやるとうまくいくと思います。