yukicoder : No.281 門松と魔法(1)

門松問題は次の正月まで来ないと思っていた。
http://yukicoder.me/problems/661

問題

長さH[0],H[1],H[2]の竹が順に並んでいる。
魔法を１回使うと、どれかの丈の長さをD縮められる(既に長さがD以下の場合は0になる)。

この３本の竹の長さが門松列(3つの値がすべて異なり、真ん中が最大または最小)を成すために必要な最少魔法回数を求めよ。

解法

H[1]が最大になるケースと最小になるケースそれぞれで必要な魔法回数を求める。

• H[1]が最小のケース
  • H[0]==H[2]ならとりあえず片方１回魔法をかけておく
  • H[1]がmin(H[0],H[2])未満になるまで魔法をかける
  • 結果が門松列かチェックする
• H[1]が最大のケース
  • H[0],H[2]がH[1]未満になるまで魔法をかける
  • H[0]==H[2]なら、片方もう１回魔法をかけておく
  • 結果が門松列かチェックする

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という関数をライブラリ化した。