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: