kmjp's blog

競技プログラミング参加記です

yukicoder : No.1991 Secret Garden

コードは短い。
https://yukicoder.me/problems/no/1991

問題

1~Nの高さの花を、座標1~Nのそれぞれに1本ずつ任意の順で植える。
f(x) := 座標xの位置に植えた花の高さ
とする。座標xに植えた花が見えないとは、正整数iに対し

  • f(x-i) ≧ f(x)+i を満たすiが1個以上ある
  • f(x+i) ≧ f(x)+i を満たすiが1個以上ある

を両方満たすものとする。Nに対し、見えない花の最大値は何本か。

解法

k本だけ花が見えるようにするとき、N本の花を配置できるか、kを小さい順に確認しよう。
高さ(N-k+1)以上の花を見えるようにし、(N-k)以下の花を見えないようにしたい。

見える花を....(N-4),(N-2),N,(N-1),(N-3),...のように配置し、間に高さ(N-k)以下の花を何本ずつ置けるかを計算していけば、合計何本の花を置けるか計算できる。
Nの上限は大きいが、それでも解は2桁で収まる。

ll N;

int ok(ll v) {
	ll cur=N-v;
	for(ll b=N-1;b>N-v;b--) {
		ll c=min(b+2,N);
		ll space=b-cur+c-cur-1;
		cur-=space;
		if(cur<=0) return 1;
	}
	return 0;
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	for(i=1;i<=N;i++) {
		if(ok(i)) {
			cout<<N-i<<endl;
			return;
		}
	}
}

まとめ

★4の割にはすんなりだった。