門松問題は次の正月まで来ないと思っていた。
http://yukicoder.me/problems/661
問題
長さH[0],H[1],H[2]の竹が順に並んでいる。
魔法を1回使うと、どれかの丈の長さをD縮められる(既に長さがD以下の場合は0になる)。
この3本の竹の長さが門松列(3つの値がすべて異なり、真ん中が最大または最小)を成すために必要な最少魔法回数を求めよ。
解法
H[1]が最大になるケースと最小になるケースそれぞれで必要な魔法回数を求める。
- H[1]が最小のケース
- H[0]==H[2]ならとりあえず片方1回魔法をかけておく
- H[1]がmin(H[0],H[2])未満になるまで魔法をかける
- 結果が門松列かチェックする
- H[1]が最大のケース
- H[0],H[2]がH[1]未満になるまで魔法をかける
- H[0]==H[2]なら、片方もう1回魔法をかけておく
- 結果が門松列かチェックする
int D; int H[3],H2[3]; int ret=2e9; int iskado(int a,int b,int c) { if(a!=c && a<b && c<b) return 1; if(a!=c && a>b && c>b) return 1; return 0; } void solve() { int i,j,k,l,r,x,y; string s; cin>>D; FOR(i,3) cin>>H[i],H2[i]=H[i]; if(D==0) { if(iskado(H[0],H[1],H[2])) ret=0; } else { // up x = max(0, (H[0]-H[1]+1+(D-1))/D); y = max(0, (H[2]-H[1]+1+(D-1))/D); H[0]=max(0,H[0]-x*D); H[2]=max(0,H[2]-y*D); if(H[0]==H[2] && H[0]!=0) x++, H[0]=max(0,H[0]-D); if(iskado(H[0],H[1],H[2])) ret=min(ret,x+y); // down FOR(i,3) H[i]=H2[i]; x=0; if(H[0]==H[2]) x++,H[2]=max(0,H[2]-D); if(H[0]>H[2]) swap(H[0],H[2]); y = max(0, (H[1]-H[0]+1+(D-1))/D); H[1]-=y*D; if(H[1]>=0 && iskado(H[0],H[1],H[2])) ret=min(ret,x+y); } if(ret==2e9) ret=-1; cout<<ret<<endl; }
まとめ
iskadoという関数をライブラリ化した。