倉庫のベルトの上に、番号札のついた箱が n 個一列に並んでいた。 ロボットが q 個の作業を順に行い、今は作業記録と、すべての作業を終えたあとの列だけが残っている。 位置は、その作業を行うときの列で先頭の箱を 1 として数える。 S i j は i 番目の箱と j 番目の箱を入れ替えた作業である。 M i j は i 番目の箱を取り出し（後ろの箱は一つずつ前に詰まる）、その箱が新しい列の j 番目になるように差し込んだ作業である。 L k は先頭の箱を外して末尾に置くことを k 回行った作業である。 F i j は i 番目から j 番目までの箱をその場で逆順にした作業である。 一行目に n と q が与えられる。 二行目に、すべての作業を終えたあとの列が先頭の箱から番号札 n 個で与えられる。 続く q 行に作業が一行に一つずつ、ロボットが行った順に与えられる。 最後の行に整数 t が与えられる。 一行の中の値は空白一つで区切られる。 一行目に t 番目の作業を行う直前の列を、二行目に最初の作業を行う前の最初の列を出力せよ。 列は先頭の箱から番号札を空白一つで区切って書く。 記録を最後の作業から最初の作業まで逆にたどり、作業ごとにその作業を元に戻せばよい。
入力
1 ≤ n ≤ 1,000。 1 ≤ q ≤ 2,000。 番号札は 1 以上 1,000,000 以下の整数で（カンマなしの数字だけで与えられる）、同じ番号札が複数あることがある。 S と M は 1 ≤ i ≤ n、1 ≤ j ≤ n（i と j が同じこともある）。 F は 1 ≤ i ≤ j ≤ n。 L は 1 ≤ k ≤ n。 1 ≤ t ≤ q
出力
二行。 一行目は t 番目の作業の直前の列、二行目は最初の列（番号札 n 個ずつ）
例 1 · stdin
5 4
30 20 50 10 40
M 1 4
L 2
S 1 5
F 2 4
3
stdout
40 10 50 20 30
10 20 30 40 50
main.py
エラー一覧00F8 ↓ · ⇧F8 ↑
入力(stdin)
実行すると、これらの行が順に input()・標準入力に渡されます(実行中に入力を求めません)。
$ 準備完了
コードを入力して解くにはパソコンで開いてください。モバイルでは問題と解答を見られます。
ほかの言語では？言語別の解答を見る · 8 言語の解答
逆向きに回るループは言語ごとに違います。 Python は for idx in range(q - 1, -1, -1) で、終わりの値は含まれないので、0 番まで回るには終わりを -1 と書きます。 range(q - 1, 0, -1) と書くと最初の作業を飛ばします。 JS・TS・Java・C#・C・C++ は for (int idx = q - 1; idx >= 0; idx--)、Craykon は 繰り返す (idx = q - 1; idx >= 0; idx--) です。 始まりを q、条件を idx > 0 と書くと、存在しない q 番を読んで 0 番を飛ばします。 C・C++ で番号を unsigned や size_t にすると、0 から 1 を引いた値がとても大きな数になって idx >= 0 がいつも真になるので、ループが終わらず配列の外を読むことになります。 C++ の ops.at(idx) はそのとき例外を投げて止まりますが、ops[idx] や C の配列では何が起こるか決まっていません。 リストを逆にしてから前から回ることもできます。 Python の reversed(ops) は逆順に回るものを返しますが、ops.reverse() はその場で逆にして None を返すので、for op in ops.reverse() は TypeError です。 JS の ops.reverse() はその場で逆にしてその配列を返します。 C++ は rbegin() から rend() まで回れます。 順番を逆にするだけでは足りず、作業ごとに反対のことをしなければなりません。 例で記録を前から戻すと、最初の列が 20 30 10 40 50 と間違います。 S と F はもう一度行えば戻りますが、M i j は j 番目から取り出して i 番目に差し込み（Python row.insert(i - 1, row.pop(j - 1))、Craykon 位置で取り除く と 挿入）、L k は末尾の k 個を先頭に持ってきます（Python row[n - k:] + row[:n - k]、Java Collections.rotate(row, k)、C++ std::rotate）。 最後に、「t 番目の作業の直前」は t 番目の作業を戻した直後です。 0 から数えるとその作業は t - 1 番なので、idx == t - 1 のときに書きます。 idx == t のときに書くと t 番目の作業を行ったあとの列が出て、t が q ならその行がまったく出ません。
Pythonmain.py · 28 行
import syslines = sys.stdin.read().split("\n")n, q = map(int, lines[0].split())row = lines[1].split()ops = [lines[2 + i].split() for i in range(q)]t = int(lines[2 + q])out = []# 마지막 작업부터 첫 작업까지 거꾸로: range의 끝 -1은 들어가지 않으므로 0번까지 돈다for idx in range(q - 1, -1, -1): op = ops[idx] a = int(op[1]) if op[0] == "S": # 맞바꾸기는 한 번 더 하면 되돌아간다 b = int(op[2]) row[a - 1], row[b - 1] = row[b - 1], row[a - 1] elif op[0] == "M": # i에서 꺼내 j에 끼웠으니, j에서 꺼내 i에 끼운다 b = int(op[2]) row.insert(a - 1, row.pop(b - 1)) elif op[0] == "L": # 앞의 a개를 뒤로 보냈으니, 뒤의 a개를 앞으로 가져온다 row = row[n - a:] + row[:n - a] else: # F: 뒤집기도 한 번 더 하면 되돌아간다 b = int(op[2]) row[a - 1:b] = row[a - 1:b][::-1] if idx == t - 1: # t번 작업을 되돌린 직후 = t번 작업을 하기 직전 out.append(" ".join(row))out.append(" ".join(row))print("\n".join(out))
JavaScriptmain.js · 29 行
const lines = require("fs").readFileSync(0, "utf8").split("\n");const [n, q] = lines[0].trim().split(/\s+/).map(Number);let row = lines[1].trim().split(/\s+/);const ops = [];for (let i = 0; i < q; i++) ops.push(lines[2 + i].trim().split(/\s+/));const t = Number(lines[2 + q]);const out = [];// 마지막 작업부터 첫 작업까지 거꾸로for (let idx = q - 1; idx >= 0; idx--) { const op = ops[idx]; const a = Number(op[1]); const b = Number(op[2]); if (op[0] === "S") { [row[a - 1], row[b - 1]] = [row[b - 1], row[a - 1]]; } else if (op[0] === "M") { // i에서 꺼내 j에 끼웠으니, j에서 꺼내 i에 끼운다 const [box] = row.splice(b - 1, 1); row.splice(a - 1, 0, box); } else if (op[0] === "L") { // 앞의 a개를 뒤로 보냈으니, 뒤의 a개를 앞으로 가져온다 row = row.slice(n - a).concat(row.slice(0, n - a)); } else { for (let l = a - 1, r = b - 1; l < r; l++, r--) [row[l], row[r]] = [row[r], row[l]]; } if (idx === t - 1) out.push(row.join(" ")); // t번 작업을 하기 직전}out.push(row.join(" "));console.log(out.join("\n"));
TypeScriptmain.ts · 31 行
import { readFileSync } from "node:fs";const lines: string[] = readFileSync(0, "utf8").split("\n");const [n, q] = lines[0].trim().split(/\s+/).map(Number);let row: string[] = lines[1].trim().split(/\s+/);const ops: string[][] = [];for (let i = 0; i < q; i++) ops.push(lines[2 + i].trim().split(/\s+/));const t: number = Number(lines[2 + q]);const out: string[] = [];// 마지막 작업부터 첫 작업까지 거꾸로for (let idx = q - 1; idx >= 0; idx--) { const op = ops[idx]; const a = Number(op[1]); const b = Number(op[2]); if (op[0] === "S") { [row[a - 1], row[b - 1]] = [row[b - 1], row[a - 1]]; } else if (op[0] === "M") { // i에서 꺼내 j에 끼웠으니, j에서 꺼내 i에 끼운다 const [box] = row.splice(b - 1, 1); row.splice(a - 1, 0, box); } else if (op[0] === "L") { // 앞의 a개를 뒤로 보냈으니, 뒤의 a개를 앞으로 가져온다 row = row.slice(n - a).concat(row.slice(0, n - a)); } else { for (let l = a - 1, r = b - 1; l < r; l++, r--) [row[l], row[r]] = [row[r], row[l]]; } if (idx === t - 1) out.push(row.join(" ")); // t번 작업을 하기 직전}out.push(row.join(" "));console.log(out.join("\n"));
JavaMain.java · 42 行
import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;import java.util.ArrayList;import java.util.Arrays;import java.util.Collections;import java.util.List;public class Main { public static void main(String[] args) throws IOException { BufferedReader in = new BufferedReader(new InputStreamReader(System.in)); String[] head = in.readLine().trim().split("\\s+"); int n = Integer.parseInt(head[0]), q = Integer.parseInt(head[1]); List<String> row = new ArrayList<>(Arrays.asList(in.readLine().trim().split("\\s+"))); String[][] ops = new String[q][]; for (int i = 0; i < q; i++) ops[i] = in.readLine().trim().split("\\s+"); int t = Integer.parseInt(in.readLine().trim()); StringBuilder out = new StringBuilder(); // 마지막 작업부터 첫 작업까지 거꾸로 for (int idx = q - 1; idx >= 0; idx--) { String[] op = ops[idx]; int a = Integer.parseInt(op[1]); switch (op[0]) { case "S": Collections.swap(row, a - 1, Integer.parseInt(op[2]) - 1); break; case "M": // i에서 꺼내 j에 끼웠으니, j에서 꺼내 i에 끼운다 row.add(a - 1, row.remove(Integer.parseInt(op[2]) - 1)); break; case "L": // 앞의 a개를 뒤로 보냈으니, 뒤의 a개를 앞으로 가져온다 Collections.rotate(row, a); break; default: Collections.reverse(row.subList(a - 1, Integer.parseInt(op[2]))); } if (idx == t - 1) out.append(String.join(" ", row)).append('\n'); // t번 작업을 하기 직전 } out.append(String.join(" ", row)).append('\n'); System.out.print(out); }}
C#Main.cs · 57 行
using System;using System.Collections.Generic;using System.Text;class Program{ static void Main() { string[] head = Console.ReadLine().Split(' ', StringSplitOptions.RemoveEmptyEntries); int n = int.Parse(head[0]), q = int.Parse(head[1]); var row = new List<string>(Console.ReadLine().Split(' ', StringSplitOptions.RemoveEmptyEntries)); var ops = new string[q][]; for (int i = 0; i < q; i++) ops[i] = Console.ReadLine().Split(' ', StringSplitOptions.RemoveEmptyEntries); int t = int.Parse(Console.ReadLine()); var sb = new StringBuilder(); // 마지막 작업부터 첫 작업까지 거꾸로 for (int idx = q - 1; idx >= 0; idx--) { string[] op = ops[idx]; int a = int.Parse(op[1]); switch (op[0]) { case "S": { int b = int.Parse(op[2]); (row[a - 1], row[b - 1]) = (row[b - 1], row[a - 1]); break; } case "M": // i에서 꺼내 j에 끼웠으니, j에서 꺼내 i에 끼운다 { int b = int.Parse(op[2]); string box = row[b - 1]; row.RemoveAt(b - 1); row.Insert(a - 1, box); break; } case "L": // 앞의 a개를 뒤로 보냈으니, 뒤의 a개를 앞으로 가져온다 { List<string> tail = row.GetRange(n - a, a); row.RemoveRange(n - a, a); row.InsertRange(0, tail); break; } default: { int b = int.Parse(op[2]); row.Reverse(a - 1, b - a + 1); // (시작 자리, 개수) break; } } if (idx == t - 1) sb.Append(string.Join(" ", row)).Append('\n'); // t번 작업을 하기 직전 } sb.Append(string.Join(" ", row)).Append('\n'); Console.Write(sb); }}
C++main.cpp · 49 行
#include <algorithm>#include <iostream>#include <vector>struct Op { char kind; int a, b;};static void printRow(const std::vector<int>& row) { for (size_t i = 0; i < row.size(); i++) std::cout << (i ? " " : "") << row[i]; std::cout << '\n';}int main() { std::ios::sync_with_stdio(false); std::cin.tie(nullptr); int n, q, t; std::cin >> n >> q; std::vector<int> row(n); for (int& x : row) std::cin >> x; std::vector<Op> ops(q); for (Op& op : ops) { std::cin >> op.kind >> op.a; op.b = 0; if (op.kind != 'L') std::cin >> op.b; } std::cin >> t; // 마지막 작업부터 첫 작업까지 거꾸로 for (int idx = q - 1; idx >= 0; idx--) { const Op& op = ops[idx]; if (op.kind == 'S') { std::swap(row[op.a - 1], row[op.b - 1]); } else if (op.kind == 'M') { // i에서 꺼내 j에 끼웠으니, j에서 꺼내 i에 끼운다 int box = row[op.b - 1]; row.erase(row.begin() + (op.b - 1)); row.insert(row.begin() + (op.a - 1), box); } else if (op.kind == 'L') { // 앞의 a개를 뒤로 보냈으니, 뒤의 a개를 앞으로 가져온다 std::rotate(row.begin(), row.end() - op.a, row.end()); } else { std::reverse(row.begin() + (op.a - 1), row.begin() + op.b); } if (idx == t - 1) printRow(row); // t번 작업을 하기 직전 } printRow(row);}
Cmain.c · 56 行
#include <stdio.h>#include <string.h>#define MAXN 1000#define MAXQ 2000static int row[MAXN], tmp[MAXN];static char kind[MAXQ];static int pa[MAXQ], pb[MAXQ];static void print_row(int n) { for (int i = 0; i < n; i++) printf(i ? " %d" : "%d", row[i]); putchar('\n');}int main(void) { int n, q, t; scanf("%d %d", &n, &q); for (int i = 0; i < n; i++) scanf("%d", &row[i]); for (int i = 0; i < q; i++) { scanf(" %c %d", &kind[i], &pa[i]); pb[i] = 0; if (kind[i] != 'L') scanf("%d", &pb[i]); } scanf("%d", &t); /* 마지막 작업부터 첫 작업까지 거꾸로 */ for (int idx = q - 1; idx >= 0; idx--) { int a = pa[idx], b = pb[idx]; if (kind[idx] == 'S') { int x = row[a - 1]; row[a - 1] = row[b - 1]; row[b - 1] = x; } else if (kind[idx] == 'M') { /* i에서 꺼내 j에 끼웠으니, j에서 꺼내 i에 끼운다 */ int box = row[b - 1]; if (b < a) memmove(&row[b - 1], &row[b], (size_t)(a - b) * sizeof(int)); else memmove(&row[a], &row[a - 1], (size_t)(b - a) * sizeof(int)); row[a - 1] = box; } else if (kind[idx] == 'L') { /* 앞의 a개를 뒤로 보냈으니, 뒤의 a개를 앞으로 가져온다 */ memcpy(tmp, &row[n - a], (size_t)a * sizeof(int)); memcpy(tmp + a, row, (size_t)(n - a) * sizeof(int)); memcpy(row, tmp, (size_t)n * sizeof(int)); } else { for (int l = a - 1, r = b - 1; l < r; l++, r--) { int x = row[l]; row[l] = row[r]; row[r] = x; } } if (idx == t - 1) print_row(n); /* t번 작업을 하기 직전 */ } print_row(n); return 0;}
Craykonmain.cray · 60 行
head = コンソール.数読み();n = head[0];q = head[1];row = コンソール.数読み();ops = [];繰り返す (i = 0; i < q; i++){ ops.追加(コンソール.行読み().空白除去().分ける(" "));}t = コンソール.行読み().数に();// 마지막 작업부터 첫 작업까지 거꾸로繰り返す (idx = q - 1; idx >= 0; idx--){ op = ops[idx]; a = op[1].数に(); 選択 (op[0]) { 場合 "S": b = op[2].数に(); x = row[a - 1]; row[a - 1] = row[b - 1]; row[b - 1] = x; 抜ける; 場合 "M": // i에서 꺼내 j에 끼웠으니, j에서 꺼내 i에 끼운다 b = op[2].数に(); box = row[b - 1]; row.位置で取り除く(b - 1); row.挿入(a - 1, box); 抜ける; 場合 "L": // 앞의 a개를 뒤로 보냈으니, 뒤의 a개를 앞으로 가져온다 앞 = row.部分リスト(0, n - a); row = row.部分リスト(n - a, a); それぞれ (v の中 앞) { row.追加(v); } 抜ける; それ以外: l = a - 1; r = op[2].数に() - 1; 間 (l < r) { x = row[l]; row[l] = row[r]; row[r] = x; l++; r--; } 抜ける; } もし (idx == t - 1) { // t번 작업을 하기 직전 コンソール.書く(row.つなぐ(" ")); }}コンソール.書く(row.つなぐ(" "));