写真家が学生 n 人を一列に並べて集合写真を撮る。 学生にはそれぞれクラス番号があり、同じクラスの学生どうしが場所を入れ替えても同じ並び方とみなす。 そのため並び方は、クラス番号を並べた数列一つで表す。 ありうる並び方をすべて辞書順に並べる。 二つの並び方を前から比べて、初めて違う位置で番号が小さいほうが前である。 この順番は輪のようにつながっている。 いちばん最後の並び方（番号がずっと大きくならないもの）の次はいちばん最初の並び方（番号がずっと小さくならないもの）で、いちばん最初の並び方の前はいちばん最後の並び方である。 今の並び方から、m が正ならすぐ次の並び方へ m 回進み、m が負ならすぐ前の並び方へ −m 回戻る。 m が 0 ならそのままである。 そうしてたどり着いた並び方を出力せよ。 すぐ次の並び方とすぐ前の並び方を求める処理はそれぞれ関数にし、一つの数列をその場で書き換えるようにする。
入力
最初の行に T（1 ≤ T ≤ 10）。 続いて並び方ごとに二行：一行目に n と m（1 ≤ n ≤ 1000、−200 ≤ m ≤ 200）、二行目にクラス番号 n 個（1 ≤ 番号 ≤ 100）
出力
並び方ごとに一行：進んだり戻ったりした後のクラス番号 n 個を空白一つで区切って出力
例 1 · stdin
4
3 1
1 3 2
3 2
3 2 1
3 -1
1 2 2
3 -2
1 3 2
stdout
2 1 3
1 3 2
2 2 1
3 2 1
main.py
エラー一覧00F8 ↓ · ⇧F8 ↑
入力(stdin)
実行すると、これらの行が順に input()・標準入力に渡されます(実行中に入力を求めません)。
$ 準備完了
コードを入力して解くにはパソコンで開いてください。モバイルでは問題と解答を見られます。
ほかの言語では？言語別の解答を見る · 8 言語の解答
すぐ次の並び方は三つの手順です。 後ろから見て初めて a[i] < a[i+1] となる i を探し、その後ろで a[i] より大きい数のうちいちばん後ろの a[j] と入れ替え、i+1 から最後までを反転します。 入れ替えた後の後ろ側はいつも降順なので、並べ替えずに反転するだけでいちばん小さい形になります。 i がなければ（ずっと下がっていれば）最後の並び方で、全体を反転すると最初の並び方です。 すぐ前の並び方は比較をすべて逆にします。 初めて a[i] > a[i+1] となる i を探し、その後ろで a[i] より小さい数のうちいちばん後ろのものと入れ替えてから後ろ側を反転します。 i がなければ（ずっと上がっていれば）最初の並び方で、全体を反転すると最後です。 「一部だけ反転」は言語ごとに違います。 C++ std::reverse(a.begin() + i + 1, a.end()) は半開区間で、標準ライブラリの std::next_permutation・std::prev_permutation がこの処理を丸ごとしてくれます（端に着くと反対側の端に変えて false を返します）。 C# Array.Reverse(a, 開始, 個数) の三つ目の値は個数なので、終わりの位置を渡すと範囲を超えて ArgumentException が出ます。 Java は Collections.reverse(list.subList(i + 1, n)) が元のリストを反転しますが int[] にはないので、両端を入れ替えながら狭めていきます。 C も同じです。 Craykon の リスト.逆に() はリスト全体しか反転しないので、区間は両端を入れ替える 間 ループで反転します。 落とし穴は六つ：① Python a[i + 1:].reverse() と JS・TS a.slice(i + 1).reverse() はコピーを反転するので、元の a はそのままです。 Python は a[i + 1:] = a[i + 1:][::-1] のように戻し入れます。 ② 上がる所を a[i] > a[i+1] で切ると同じ番号（2 2）を上がりとみなし、クラス番号が重なるとき並び方を飛ばしたり繰り返したりします。 等しければさらに左へ進む必要があります（>=）。 前の並び方でも同じく等しければ進みます（<=）。 ③ 入れ替える数を i のすぐ後ろから末尾に向かって探すと、「いちばん少しだけ大きい数」ではなく最初に出会った大きい数と入れ替えて、いくつもの並び方を飛ばします。 ④ 最後の並び方で何もしないと最初に戻りません。 ⑤ 次の並び方の関数を写して前の並び方を作るとき「大きい数と入れ替える」をそのまま残すと、違う並び方になります。 ⑥ for (k = 0; k < m; k++) だけだと、m が負のとき一度も回りません。
Pythonmain.py · 38 行
def next_lineup(a): """a를 사전 순으로 바로 다음 줄 세우기로 바꾼다(마지막이면 첫 줄 세우기로).""" i = len(a) - 2 while i >= 0 and a[i] >= a[i + 1]: # 뒤에서부터 처음으로 오르는 곳 i -= 1 if i < 0: # 모두 내려가면 마지막 줄 세우기 → 뒤집으면 첫 줄 세우기 a.reverse() return j = len(a) - 1 while a[j] <= a[i]: # a[i]보다 큰 수 가운데 가장 뒤의 것 j -= 1 a[i], a[j] = a[j], a[i] a[i + 1:] = a[i + 1:][::-1] # 뒤쪽 구간만 제자리에서 뒤집는다def prev_lineup(a): """a를 사전 순으로 바로 앞 줄 세우기로 바꾼다(첫 줄 세우기이면 마지막으로). 비교 방향만 거꾸로다.""" i = len(a) - 2 while i >= 0 and a[i] <= a[i + 1]: # 뒤에서부터 처음으로 내려가는 곳 i -= 1 if i < 0: # 모두 오르면 첫 줄 세우기 → 뒤집으면 마지막 줄 세우기 a.reverse() return j = len(a) - 1 while a[j] >= a[i]: # a[i]보다 작은 수 가운데 가장 뒤의 것 j -= 1 a[i], a[j] = a[j], a[i] a[i + 1:] = a[i + 1:][::-1]t = int(input())for _ in range(t): n, m = map(int, input().split()) a = list(map(int, input().split())) step = next_lineup if m > 0 else prev_lineup # m이 음수면 |m|번 앞으로 for _ in range(abs(m)): step(a) print(*a)
JavaScriptmain.js · 48 行
const data = require("fs").readFileSync(0, "utf8").trim().split(/\s+/).map(Number);// 구간 [lo, hi]를 제자리에서 뒤집는다function reverseRange(a, lo, hi) { for (; lo < hi; lo++, hi--) [a[lo], a[hi]] = [a[hi], a[lo]];}// a를 사전 순으로 바로 다음 줄 세우기로 바꾼다(마지막이면 첫 줄 세우기로)function nextLineup(a) { let i = a.length - 2; while (i >= 0 && a[i] >= a[i + 1]) i--; // 뒤에서부터 처음으로 오르는 곳 if (i < 0) { a.reverse(); // 모두 내려가면 마지막 → 뒤집으면 첫 줄 세우기 return; } let j = a.length - 1; while (a[j] <= a[i]) j--; // a[i]보다 큰 수 가운데 가장 뒤의 것 [a[i], a[j]] = [a[j], a[i]]; reverseRange(a, i + 1, a.length - 1);}// a를 사전 순으로 바로 앞 줄 세우기로 바꾼다(첫 줄 세우기이면 마지막으로). 비교 방향만 거꾸로다function prevLineup(a) { let i = a.length - 2; while (i >= 0 && a[i] <= a[i + 1]) i--; // 뒤에서부터 처음으로 내려가는 곳 if (i < 0) { a.reverse(); // 모두 오르면 첫 줄 세우기 → 뒤집으면 마지막 return; } let j = a.length - 1; while (a[j] >= a[i]) j--; // a[i]보다 작은 수 가운데 가장 뒤의 것 [a[i], a[j]] = [a[j], a[i]]; reverseRange(a, i + 1, a.length - 1);}let p = 0;const t = data[p++];const out = [];for (let c = 0; c < t; c++) { const n = data[p++]; const m = data[p++]; const a = data.slice(p, p + n); p += n; const step = m > 0 ? nextLineup : prevLineup; // m이 음수면 |m|번 앞으로 for (let k = 0; k < Math.abs(m); k++) step(a); out.push(a.join(" "));}console.log(out.join("\n"));
TypeScriptmain.ts · 49 行
import { readFileSync } from "node:fs";const data: number[] = readFileSync(0, "utf8").trim().split(/\s+/).map(Number);// 구간 [lo, hi]를 제자리에서 뒤집는다function reverseRange(a: number[], lo: number, hi: number): void { for (; lo < hi; lo++, hi--) [a[lo], a[hi]] = [a[hi], a[lo]];}// a를 사전 순으로 바로 다음 줄 세우기로 바꾼다(마지막이면 첫 줄 세우기로)function nextLineup(a: number[]): void { let i = a.length - 2; while (i >= 0 && a[i] >= a[i + 1]) i--; // 뒤에서부터 처음으로 오르는 곳 if (i < 0) { a.reverse(); // 모두 내려가면 마지막 → 뒤집으면 첫 줄 세우기 return; } let j = a.length - 1; while (a[j] <= a[i]) j--; // a[i]보다 큰 수 가운데 가장 뒤의 것 [a[i], a[j]] = [a[j], a[i]]; reverseRange(a, i + 1, a.length - 1);}// a를 사전 순으로 바로 앞 줄 세우기로 바꾼다(첫 줄 세우기이면 마지막으로). 비교 방향만 거꾸로다function prevLineup(a: number[]): void { let i = a.length - 2; while (i >= 0 && a[i] <= a[i + 1]) i--; // 뒤에서부터 처음으로 내려가는 곳 if (i < 0) { a.reverse(); // 모두 오르면 첫 줄 세우기 → 뒤집으면 마지막 return; } let j = a.length - 1; while (a[j] >= a[i]) j--; // a[i]보다 작은 수 가운데 가장 뒤의 것 [a[i], a[j]] = [a[j], a[i]]; reverseRange(a, i + 1, a.length - 1);}let p = 0;const t = data[p++];const out: string[] = [];for (let c = 0; c < t; c++) { const n = data[p++]; const m = data[p++]; const a = data.slice(p, p + n); p += n; const step = m > 0 ? nextLineup : prevLineup; // m이 음수면 |m|번 앞으로 for (let k = 0; k < Math.abs(m); k++) step(a); out.push(a.join(" "));}console.log(out.join("\n"));
JavaMain.java · 64 行
import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;import java.util.StringTokenizer;public class Main { static void swap(int[] a, int x, int y) { int tmp = a[x]; a[x] = a[y]; a[y] = tmp; } // 구간 [lo, hi]를 제자리에서 뒤집는다 static void reverseRange(int[] a, int lo, int hi) { for (; lo < hi; lo++, hi--) swap(a, lo, hi); } // a를 사전 순으로 바로 다음 줄 세우기로 바꾼다(마지막이면 첫 줄 세우기로) static void nextLineup(int[] a) { int i = a.length - 2; while (i >= 0 && a[i] >= a[i + 1]) i--; // 뒤에서부터 처음으로 오르는 곳 if (i < 0) { reverseRange(a, 0, a.length - 1); // 마지막 → 뒤집으면 첫 줄 세우기 return; } int j = a.length - 1; while (a[j] <= a[i]) j--; // a[i]보다 큰 수 가운데 가장 뒤의 것 swap(a, i, j); reverseRange(a, i + 1, a.length - 1); } // a를 사전 순으로 바로 앞 줄 세우기로 바꾼다(첫 줄 세우기이면 마지막으로). 비교 방향만 거꾸로다 static void prevLineup(int[] a) { int i = a.length - 2; while (i >= 0 && a[i] <= a[i + 1]) i--; // 뒤에서부터 처음으로 내려가는 곳 if (i < 0) { reverseRange(a, 0, a.length - 1); // 첫 줄 세우기 → 뒤집으면 마지막 return; } int j = a.length - 1; while (a[j] >= a[i]) j--; // a[i]보다 작은 수 가운데 가장 뒤의 것 swap(a, i, j); reverseRange(a, i + 1, a.length - 1); } public static void main(String[] args) throws IOException { BufferedReader in = new BufferedReader(new InputStreamReader(System.in)); int t = Integer.parseInt(in.readLine().trim()); StringBuilder out = new StringBuilder(); for (int c = 0; c < t; c++) { StringTokenizer st = new StringTokenizer(in.readLine()); int n = Integer.parseInt(st.nextToken()); int m = Integer.parseInt(st.nextToken()); int[] a = new int[n]; st = new StringTokenizer(in.readLine()); for (int k = 0; k < n; k++) a[k] = Integer.parseInt(st.nextToken()); for (int k = 0; k < m; k++) nextLineup(a); for (int k = 0; k < -m; k++) prevLineup(a); // m이 음수면 |m|번 앞으로 for (int k = 0; k < n; k++) out.append(k > 0 ? " " : "").append(a[k]); out.append('\n'); } System.out.print(out); }}
C#Main.cs · 55 行
using System;using System.Linq;using System.Text;class Program{ // a를 사전 순으로 바로 다음 줄 세우기로 바꾼다(마지막이면 첫 줄 세우기로) static void NextLineup(int[] a) { int i = a.Length - 2; while (i >= 0 && a[i] >= a[i + 1]) i--; // 뒤에서부터 처음으로 오르는 곳 if (i < 0) { Array.Reverse(a); // 마지막 → 뒤집으면 첫 줄 세우기 return; } int j = a.Length - 1; while (a[j] <= a[i]) j--; // a[i]보다 큰 수 가운데 가장 뒤의 것 (a[i], a[j]) = (a[j], a[i]); // Array.Reverse(배열, 시작, 개수) — 셋째 값은 끝 자리가 아니라 개수다 Array.Reverse(a, i + 1, a.Length - (i + 1)); } // a를 사전 순으로 바로 앞 줄 세우기로 바꾼다(첫 줄 세우기이면 마지막으로). 비교 방향만 거꾸로다 static void PrevLineup(int[] a) { int i = a.Length - 2; while (i >= 0 && a[i] <= a[i + 1]) i--; // 뒤에서부터 처음으로 내려가는 곳 if (i < 0) { Array.Reverse(a); // 첫 줄 세우기 → 뒤집으면 마지막 return; } int j = a.Length - 1; while (a[j] >= a[i]) j--; // a[i]보다 작은 수 가운데 가장 뒤의 것 (a[i], a[j]) = (a[j], a[i]); Array.Reverse(a, i + 1, a.Length - (i + 1)); } static void Main() { int t = int.Parse(Console.ReadLine()!.Trim()); var output = new StringBuilder(); for (int c = 0; c < t; c++) { int[] nm = Console.ReadLine()!.Trim().Split(' ').Select(int.Parse).ToArray(); int[] a = Console.ReadLine()!.Trim().Split(' ').Select(int.Parse).ToArray(); int m = nm[1]; for (int k = 0; k < m; k++) NextLineup(a); for (int k = 0; k < -m; k++) PrevLineup(a); // m이 음수면 |m|번 앞으로 output.Append(string.Join(" ", a)).Append('\n'); } Console.Write(output); }}
C++main.cpp · 49 行
#include <algorithm>#include <iostream>#include <vector>// a를 사전 순으로 바로 다음 줄 세우기로 바꾼다(마지막이면 첫 줄 세우기로)// (표준 라이브러리 std::next_permutation이 바로 이 일을 한다 — 여기서는 직접 쓴다)void nextLineup(std::vector<int>& a) { int i = (int)a.size() - 2; while (i >= 0 && a[i] >= a[i + 1]) i--; // 뒤에서부터 처음으로 오르는 곳 if (i < 0) { std::reverse(a.begin(), a.end()); // 마지막 → 뒤집으면 첫 줄 세우기 return; } int j = (int)a.size() - 1; while (a[j] <= a[i]) j--; // a[i]보다 큰 수 가운데 가장 뒤의 것 std::swap(a[i], a[j]); std::reverse(a.begin() + i + 1, a.end()); // [시작, 끝) 반열린 구간}// a를 사전 순으로 바로 앞 줄 세우기로 바꾼다(첫 줄 세우기이면 마지막으로). 비교 방향만 거꾸로다// (std::prev_permutation이 이 일을 한다)void prevLineup(std::vector<int>& a) { int i = (int)a.size() - 2; while (i >= 0 && a[i] <= a[i + 1]) i--; // 뒤에서부터 처음으로 내려가는 곳 if (i < 0) { std::reverse(a.begin(), a.end()); // 첫 줄 세우기 → 뒤집으면 마지막 return; } int j = (int)a.size() - 1; while (a[j] >= a[i]) j--; // a[i]보다 작은 수 가운데 가장 뒤의 것 std::swap(a[i], a[j]); std::reverse(a.begin() + i + 1, a.end());}int main() { std::ios::sync_with_stdio(false); int t; std::cin >> t; while (t--) { int n, m; std::cin >> n >> m; std::vector<int> a(n); for (int& x : a) std::cin >> x; for (int k = 0; k < m; k++) nextLineup(a); for (int k = 0; k < -m; k++) prevLineup(a); // m이 음수면 |m|번 앞으로 for (int k = 0; k < n; k++) std::cout << (k ? " " : "") << a[k]; std::cout << '\n'; }}
Cmain.c · 56 行
#include <stdio.h>static void swap(int *x, int *y) { int tmp = *x; *x = *y; *y = tmp;}/* 구간 [lo, hi]를 제자리에서 뒤집는다 */static void reverse_range(int *a, int lo, int hi) { for (; lo < hi; lo++, hi--) swap(&a[lo], &a[hi]);}/* a를 사전 순으로 바로 다음 줄 세우기로 바꾼다(마지막이면 첫 줄 세우기로) */static void next_lineup(int *a, int n) { int i = n - 2; while (i >= 0 && a[i] >= a[i + 1]) i--; /* 뒤에서부터 처음으로 오르는 곳 */ if (i < 0) { reverse_range(a, 0, n - 1); /* 마지막 → 뒤집으면 첫 줄 세우기 */ return; } int j = n - 1; while (a[j] <= a[i]) j--; /* a[i]보다 큰 수 가운데 가장 뒤의 것 */ swap(&a[i], &a[j]); reverse_range(a, i + 1, n - 1);}/* a를 사전 순으로 바로 앞 줄 세우기로 바꾼다(첫 줄 세우기이면 마지막으로). 비교 방향만 거꾸로다 */static void prev_lineup(int *a, int n) { int i = n - 2; while (i >= 0 && a[i] <= a[i + 1]) i--; /* 뒤에서부터 처음으로 내려가는 곳 */ if (i < 0) { reverse_range(a, 0, n - 1); /* 첫 줄 세우기 → 뒤집으면 마지막 */ return; } int j = n - 1; while (a[j] >= a[i]) j--; /* a[i]보다 작은 수 가운데 가장 뒤의 것 */ swap(&a[i], &a[j]); reverse_range(a, i + 1, n - 1);}int main(void) { int t; scanf("%d", &t); static int a[1000]; while (t--) { int n, m; scanf("%d %d", &n, &m); for (int k = 0; k < n; k++) scanf("%d", &a[k]); for (int k = 0; k < m; k++) next_lineup(a, n); for (int k = 0; k < -m; k++) prev_lineup(a, n); /* m이 음수면 |m|번 앞으로 */ for (int k = 0; k < n; k++) printf(k ? " %d" : "%d", a[k]); printf("\n"); } return 0;}
Craykonmain.cray · 77 行
// 구간 [lo, hi]를 제자리에서 뒤집는다(목록.뒤집기()는 목록 전체만 뒤집는다)구간뒤집기(a, lo, hi){ 間 (lo < hi) { tmp = a[lo]; a[lo] = a[hi]; a[hi] = tmp; lo += 1; hi -= 1; }}// a를 사전 순으로 바로 다음 줄 세우기로 바꾼다(마지막이면 첫 줄 세우기로)다음줄(a){ i = a.個数 - 2; 間 (i >= 0 && a[i] >= a[i + 1]) { i -= 1; } もし (i < 0) { a.逆に(); // 마지막 → 뒤집으면 첫 줄 세우기 返す; } j = a.個数 - 1; 間 (a[j] <= a[i]) { j -= 1; } tmp = a[i]; a[i] = a[j]; a[j] = tmp; 구간뒤집기(a, i + 1, a.個数 - 1);}// a를 사전 순으로 바로 앞 줄 세우기로 바꾼다(첫 줄 세우기이면 마지막으로). 비교 방향만 거꾸로다앞줄(a){ i = a.個数 - 2; 間 (i >= 0 && a[i] <= a[i + 1]) { i -= 1; } もし (i < 0) { a.逆に(); // 첫 줄 세우기 → 뒤집으면 마지막 返す; } j = a.個数 - 1; 間 (a[j] >= a[i]) { j -= 1; } tmp = a[i]; a[i] = a[j]; a[j] = tmp; 구간뒤집기(a, i + 1, a.個数 - 1);}t = コンソール.行読み().空白除去().数に();繰り返す (c = 0; c < t; c++){ nm = コンソール.数読み(); a = コンソール.数読み(); m = nm[1]; 繰り返す (k = 0; k < m; k++) { 다음줄(a); } 繰り返す (k = 0; k < -m; k++) { 앞줄(a); } コンソール.書く(a.つなぐ(" "));}