コードは短い。
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の割にはすんなりだった。