yukicoder : No.1379 Postponed

シンプルな問題設定で良いね。
https://yukicoder.me/problems/no/1379

問題

昇順である正整数列Aが与えられる。
Aの先頭(A[0]+1)要素を左にrotateする、という処理をK回繰り返す。
最終的に得られる数列を求めよ。

解法

A[0]がK回後どこに行くかを考える。
A[1]以降はA[0]より大きいので、最初A[0]にあったものは、周期(A[0]+1)でグルグル回る。
よって、A[0]がどこに行くかを求めることができた。

次に、初期状態からA[0]を取り除き、またA[0]が左端に来ていた時のceil(K/(A[0]+1))を減じた処理回数について、同様にA[0](元A[1])がどこに行くかを考える、ということを繰り返そう。

int N;
ll K;
int A[1010];

vector<int> hoge(vector<int> A,ll K) {
	if(A.size()==1 || A[0]<=0) return A;
	
	ll go=(K+A[0])/(A[0]+1);
	vector<int> B=A;
	B.erase(B.begin());
	FORR(b,B) b--;
	vector<int> R=hoge(B,K-go);
	FORR(b,R) b++;
	ll lef=K%(A[0]+1);
	int pos=(lef==0?0:(A[0]+1-lef));
	R.insert(R.begin()+pos,A[0]);
	return R;
	
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>K;
	vector<int> A(N);
	FOR(i,N) cin>>A[i];
	
	auto B=hoge(A,K);
	FORR(b,B) cout<<b<<" ";
	cout<<endl;
	
}

まとめ

面白い問題。