(4)は真面目にやらずに離脱。(3)までは解けたので良かったね。
https://www.hackerrank.com/contests/lay-contest-00004/challenges/2-12
問題
H*Wのグリッド状の敷地について、各セルの高さH[r][c]が与えられる。
各セルの高さを1上げるにはコストA、1下げるにはコストB、1か所を1上げ別の場所を下げるにはコストGかかる。
全セルの高さを揃えるのにかかる最小コストを求めよ。
解法
Hの範囲は狭いので、min(H)~max(H)の範囲でそろえる高さを総当たりしよう。
揃える高さhが決まると、Hを事前にソートしておくことで、hより高さが大きいセルなので減らさないといけない高さの総和sumDと、高さが小さいセルなので増さないといけない高さの総和sumIが求まる。
G<A+Bならmin(sumD,sumI)分だけコストGによる高さの増減を行い、残った高さはコストA,Bの手段で高さを均せばよい。
int T; int H,W,N; ll A,B,G; ll HH[10101]; ll S[10101]; void solve() { int i,j,k,l,r,x,y; string s; cin>>T; while(T--) { cin>>H>>W>>A>>B>>G; N=H*W; FOR(x,N) cin>>HH[x]; sort(HH,HH+N); FOR(x,N) S[x+1]=S[x]+HH[x]; ll ret=1LL<<60; for(i=-100000;i<=100000;i++) { j=lower_bound(HH,HH+N,i)-HH; ll pl=(S[N]-S[j])-1LL*i*(N-j); ll mi=1LL*i*j-(S[j]-S[0]); ll tot=0; if(A+B>G) { ll a=min(pl,mi); tot += G*a; pl-=a; mi-=a; } tot += A*mi+B*pl; ret=min(ret,tot); } cout<<ret<<endl; } }
まとめ
またこれ何かのゲームが元ネタだったりするのかな。
ポピュラスとかシムシティとか…でも増減を同時に行うオペレーションってなさそう。