Official

A - Range Swap Editorial by mechanicalpenciI


\(P\)番目から\(Q\)番目までの項と\(R\)番目から\(S\)番目までの項を入れ替えると、

\[ A_1,A_2,\ldots, A_{P-1}, A_P,A_{P+1},\ldots, A_{Q-1}, A_Q, A_{Q+1}, \ldots, A_{R-1}, A_R, A_{R+1}, \ldots, A_{S-1}, A_S, A_{S+1}, \ldots, A_{N-1}, A_N \\ \to A_1,A_2,\ldots, A_{P-1}, A_R,A_{R+1},\ldots, A_{S-1}, A_S, A_{Q+1}, \ldots, A_{R-1}, A_P, A_{P+1}, \ldots, A_{Q-1}, A_Q, A_{S+1}, \ldots, A_{N-1}, A_N \]

となります。\(S-R=Q-P\)である事から交換される要素以外の添字が変わる事はなく、よって、

\[ B_i= \begin{cases} A_i &(i<P のとき) \\ A_{i+(R-P)} &(P\leq i\leq Q のとき) \\ A_i &(Q<i<R のとき) \\ A_{i+(P-R)} &(R\leq i\leq S のとき) \\ A_i &(S<iのとき) \\ \end{cases} \]

とすれば良いです。 これは、for文とif文を用いて実装する事ができます。

また、\(Q-P=S-R\) である事から\(i=0,1,\ldots, Q-P\) について \(A_{P+i}\)\(A_{R+i}\)を交換する事によっても答えを求める事ができます。

c++ による実装例 \(1\) :

#include <bits/stdc++.h>
using namespace std;

int main() {
	int n,p,q,r,s;
	int a[101];

	cin>>n>>p>>q>>r>>s;
	for(int i=1;i<=n;i++)cin>>a[i];
	
	for(int i=1;i<=n;i++){
		if((p<=i)&&(i<=q))cout<<a[i+r-p];
		else if((r<=i)&&(i<=s))cout<<a[i+p-r];
		else cout<<a[i];
		if(i<n)cout<<" ";
		else cout<<endl; 
	}

	return 0;
}

c++ による実装例 \(2\) :

#include <bits/stdc++.h>
using namespace std;

int main() {
	int n,p,q,r,s;
	int a[100];

	cin>>n>>p>>q>>r>>s;
	for(int i=0;i<n;i++)cin>>a[i];
	
	for(int i=p;i<=q;i++)swap(a[i-1],a[r-p+i-1]);

	for(int i=0;i<n;i++){
		cout<<a[i];
		if(i<(n-1))cout<<" ";
		else cout<<endl; 
	}

	return 0;
}

Pythonによる実装例 :

n,p,q,r,s= map(int, input().split())
a=list(map(int, input().split()))

for i in range(p,q+1):
    a[i-1],a[r-p+i-1]=a[r-p+i-1],a[i-1]
    
print(*a)

posted:
last update: