超初心者が競プロに挑む

初心者からの競プロ練習記録

ARC073Eメモ

ARC073Eで気になるところをメモ
A,Bという同じ長さの配列がある時に、あるiでA[i]とB[i]を入れ替えるという操作を繰り返して
A中の最大値と最小値の差を最小化するという時のアルゴリズムのこと

A=[8,4,4,4,1]
B=[4,0,0,0,4]
Aの最大値と最小値の差は8-1=7

A=[4,4,4,4,4]
B=[8,0,0,0,1]
Aの最大値と最小値の差は4-4=0
みたいにすること
こういうことは、「⓵各iに対するA[i]とB[i]のペアについてA[i]がB[i]以下になるように入れ替え⓶配列Aの中で最小値をとるA[i]がB[i]よりも小さかったら入れ替える」という操作の繰り返しをして、探すことができる。
1
A=[4,0,0,0,1]
B=[8,4,4,4,4]
2
A=[4,4,4,4,1]
B=[8,0,0,0,4]

A=[4,4,4,4,4]
B=[8,0,0,0,1]
終了
でこれはset(ヒープ)を使ってN logNで可能。
⓵の操作のあと、MAX(A)-min(A)が変化するのは⓶の操作をした時のみなので、これで必ず最小となるものを求められる。仮に、最小でないもので入れ替えをしてもmin(A)は変わらないし、MAX(A)が小さくなることはありえなく、その後⓶の操作をしなければならないので、結局⓶の操作だけで十分。疑似コードは以下のような感じ。

H = 昇順ヒープ
DifMin = 適当に大きな値
for i in 1..N:
  H.push({A[i],i})
while True:
  DifMin = min(DifMin, H.last.first - H.begin.first)
  if H.beginが交換をしても効果がない:
    break
  i = H.begin.second
  H.erase( H.begin.first )
  H.push( {B[i], i})
求めたい値=DifMin

ARCとかの解説を読むと、こうゆう「これくらいできるでしょ😐」ってサラッて書かれている場所こそよくわからなかったりするんですよね😞