Google Code Jam 2021 Qualification Round : A. Reversort, C. Reversort Engineering

今年も始まりました。
https://codingcompetitions.withgoogle.com/codejam/round/000000000043580a/00000000006d0a5c
https://codingcompetitions.withgoogle.com/codejam/round/000000000043580a/00000000006d12d7

問題

1～NのPermutation Pに対し、Reversortとそのコストは、以下の手順で与えられる。

P[i]をiの昇順に合わせていくことを考える(P[i-1]以前はソート済みとする)。
P[i]を定めるとき、i番目以降の要素のうち最小値をP[j]とする。
その時、コスト(j-i+1)をかけP[i...j]を反転させる。

(A問題) Pが与えられるので、コストを求めよ。
(C問題) コストが与えられるので、Pを構築せよ。

解法

コストの計算は、愚直に行ってもO(N^2)で終わるので愚直にやればよい。

コストからPの計算は、ソート済みのPかを逆にかき回す順で構築しよう。
iを降順に行い、残コストCに対しj=min(N-1,i+C-1)としてP[i...j]を反転させていこう。

void solve(int _loop) {
	int f,i,j,k,l,x,y;
	int N;
	int L[101];
	cin>>N;
	FOR(i,N) cin>>L[i];
	int ret=0;
	FOR(i,N-1) {
		int mi=i;
		for(j=i;j<N;j++) if(L[j]<L[mi]) mi=j;
		ret+=mi-i+1;
		reverse(L+i,L+mi+1);
	}
	
	_P("Case #%d: %d\n",_loop, ret);
}

void solve(int _loop) {
	int f,i,j,k,l,x,y;
	
	int N,C;
	cin>>N>>C;
	C-=(N-1);
	int L[101];
	if(C<0) {
		_P("Case #%d: IMPOSSIBLE\n",_loop);
		return;
	}
	
	FOR(i,N) L[i]=i+1;
	for(i=N-2;i>=0;i--) {
		x=min(C,N-1-i);
		reverse(L+i,L+i+x+1);
		C-=x;
	}
	if(C!=0) {
		_P("Case #%d: IMPOSSIBLE\n",_loop);
		return;
	}
	
	_P("Case #%d:",_loop);
	FOR(i,N) _P(" %d",L[i]);
	_P("\n");
	
}

まとめ

ここら辺は問題なし。