AtCoder ARC #204 : D - Favorite Interval

コードは短いが、頭がこんがらがりそうな問題。
https://atcoder.jp/contests/arc204/tasks/arc204_d

問題

整数N,L,Rが与えられる。
以下を満たす(R-L)～(N-1)の順列Pが存在するなら1つ答えよ。

Aを0～(N-1)の順列とする。
i=0～(|P|-1)の順で以下を行う。x=P[i] % |A|とすると、A[x]を削除し間を詰める。
最終的にA=(L,L+1,...,R-1)となる。

解法

• R-L＜Lの場合
  • N＞Rの間は、Pに順にN-1を詰めるとNが1小さい問題に帰着できる。
  • N=Rとすると、初手でPに(R-L)を詰めると、R-L＜LよりA[L]の手前の要素を1個消せる。あとはPに(N-1),(N-2),....と選択すると、A[L]の手前の要素を順次消せる
• R-L≧Lの場合
  • A[L]の手前の要素数をx、A[R-1]の後の要素数をyとする。
  • 以下のようにすると、1手でxを0～(y-1)まで減らすことが出来、yを1減らせる。よってx≦y(y-1)/2なら条件を満たせる。
  • a=min(x,y-1)とし、Pに(N-a-1,N-1,N-2,...,N-a)と詰める。その際Nは(a+1)減少する。

int N,L,R;

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>L>>R;
	if(R-L<L) {
		cout<<"Yes"<<endl;
		while(N>R) {
			cout<<N-1<<" ";
			N--;
		}
		cout<<(R-L)<<" ";
		for(i=N-1;i>=R-L+1;i--) cout<<i<<" ";
		cout<<endl;
		
	}
	else {
		ll le=L,ri=N-R;
		ll sum=ri*(ri-1)/2;
		if(sum<le) {
			cout<<"No"<<endl;
		}
		else {
			cout<<"Yes"<<endl;
			while(ri) {
				ll a=min(le,ri-1);
				cout<<N-a-1<<" ";
				for(i=1;i<=a;i++) cout<<N-i<<" ";
				N-=a+1;
				ri-=1;
				le-=a;
			}
			cout<<endl;
		}
	}
}

まとめ

思ったよりシンプルな解法になるんだな。