AtCoder Regular Contest 094 E - Tozan and Gezan
問題概要
2つの数列AとBがあり、とざん君はA、げざん君はBのある1項を1減らす操作ができる。
とざん君はできるだけ2つの数列を違うものに、げざん君は同じものにしたい。何手続く？
解法
まず、A=Bなら0。
次に、両者の目的を考えると、戦略的にとざん君はA[i]>=B[i]となるA[i]は減らさない方がよい。げざん君は逆に、B[i]<=A[i]となるB[i]は減らさない方が良い。
つまり、
・とざん君=A[i]<B[i]のA[i]を減らす
・げざん君=A[i]>B[i]のB[i]を減らす
という行動を毎ターン取ることが分かる。
ここで、両者とも数列の項を減らすことしかできない。その為、A[i]>B[i]となる項を除き、残りはA[i]=B[i]=0とせざるを得ない。この時の0にならない項はA[i]>B[i]の条件を満たすminなのでそれを持ってあげて残りは全て0にするのでAの総和。
よって、Aの総和-(A[i]>B[i]を満たすB[i]のmin)によって解答が求まる。
これらを実装して、AC。
