Official
B - Flip Card Stack Editorial
by
B - Flip Card Stack Editorial
by
mechanicalpenciI
Editorial for printing
\(Q\) 回の操作を愚直にシミュレーションすることを考えます。
それぞれの時点におけるカードの山の状態を 長さ \(N\) の数列 \(A=(A_1,A_2, \ldots,A_N)\) で表すことを考えます。ここで、山の上から \(i\) 番目 \((1\leq i\leq N)\) のカードに \(X\) が書かれていて表向きに積まれているとき \(A_i=X\), 裏向きに積まれているとき \(A_i=-X\) と定義します。
最初の状態は \(A=(1,2,\ldots, N)\) と表されます。
さらに操作について、「上から \(K\) 枚のカードをひとまとめにして裏返し、元の位置に戻す」という操作は、
\(A=(A_1,A_2, \ldots,A_N)\) を、
\((-A_K,-A_{K-1},\ldots, -A_1, A_{K+1}, A_{K+2},\ldots, A_N)\) に変換する操作に対応しています。
最後に、すべての操作を終えた後の \(A_1,A_2, \ldots, A_N\) をこの順に各行に出力すれば良いです。
C++ による実装例:
#include <bits/stdc++.h>
using namespace std;
int main(void){
int n,q,x;
int a[100]={};
int b[100]={};
cin>>n>>q;
for(int j=0;j<n;j++)a[j]=j+1;
for(int i=0;i<q;i++){
cin>>x;
for(int j=0;j<x;j++)b[x-j-1]=-a[j];
for(int j=0;j<x;j++)a[j]=b[j];
}
for(int j=0;j<n;j++)cout<<a[j]<<endl;
return 0;
}
Python による実装例:
n,q=map(int,input().split())
k=list(map(int,input().split()))
a=[i+1 for i in range(n)]
b=[i+1 for i in range(n)]
for i in range(q):
for j in range(k[i]):
b[k[i]-j-1]=-a[j]
for j in range(k[i]):
a[j]=b[j]
for i in range(n):
print(a[i])
posted:
last update:
