Official

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: