{ }codelper
要素の入れ替えリストのコピーリストの走査P0176

席替えのあとで動いた生徒

教室に席が一列に n 個あり、席番号は左から 1, 2, …, n である。
一行目に n が、二行目に最初の席に座った生徒の名前 n 個が席の順に空白一つずつ区切って与えられる。
三行目に入れ替えの数 m が、続く m 行に入れ替え「i j」が一行に一つずつ与えられる。
担任の先生はこの入れ替えを与えられた順に行う。
入れ替え「i j」は、i 番の席の生徒と j 番の席の生徒が席を交換することである。
i と j が同じなら何も起こらない。
すべての入れ替えのあと、一行目に席の順に生徒の名前を空白一つずつ区切って出力せよ。
二行目には、最初の席と最後の席が違う生徒の数 k を出力せよ。
続く k 行に、そのような生徒ごとに「名前 最初の席 最後の席」を空白一つずつ区切って出力せよ。
この k 行は、最初の席番号が小さい生徒から出力する。
何度か動いても最後に最初の席に戻った生徒は数えない。
k が 0 なら二行目の 0 までだけを出力する。

入力
1 ≤ n ≤ 1000、0 ≤ m ≤ 2000、1 ≤ i, j ≤ n。
名前は英小文字 1 ～ 10 文字ですべて異なる
出力
一行目に最後の席順の名前、二行目に k、続いて k 行に「名前 最初の席 最後の席」
例 1 · stdin
5
mina joon sora dan kai
3
1 3
2 5
3 1
stdout
mina kai sora dan joon
2
joon 2 5
kai 5 2
例 2 · stdin
3
ari bo cy
3
1 2
2 3
3 1
stdout
ari cy bo
2
bo 2 3
cy 3 2
main.py
入力(stdin)

実行すると、これらの行が順に input()・標準入力に渡されます(実行中に入力を求めません)。

$ 準備完了

コードを入力して解くにはパソコンで開いてください。モバイルでは問題と解答を見られます。

ほかの言語では？言語別の解答を見る · 8 言語の解答

最初の席を残しておくには、入れ替える前にリストをコピーしなければなりません。
落とし穴その一：start = seats はコピーではなく同じリストにもう一つ名前を付けるだけなので、入れ替えが両方の名前に見え、動いた生徒がいつも 0 人になります。
Python・JS・TS・Java・C# のリストと配列、Craykon のリストはどれもこのように同じものを指します。
コピーの方法：Python seats[:]・list(seats)、JS・TS [...seats]・slice()、Java seats.clone()、C# (string[])seats.Clone()、Craykon seats.部分リスト(0, seats.個数)（韓国語 부분목록・개수）。
C++ の std::vector だけは = で要素を丸ごとコピーし、C の配列は = で代入できないので memcpy や strcpy で写します。
二つの要素の交換：Python a[i], a[j] = a[j], a[i]、JS・TS [a[i], a[j]] = [a[j], a[i]]、C# のタプル (a[i], a[j]) = (a[j], a[i])、C++ std::swap(a[i], a[j]) で、Java・C・Craykon は一時変数 tmp を使います（C の文字列は strcpy を三回）。
落とし穴その二：一時変数なしで a[i] = a[j]; a[j] = a[i]; と書くと、一行目で a[i] がもう上書きされているので二つの席が同じ名前になります。
最後に今の席を探すときは、名前 → 席の辞書を一度作れば生徒ごとに探し直さずに済みます。

Pythonmain.py · 19 行
import sys data = sys.stdin.read().split()n = int(data[0])seats = data[1:1 + n]start = seats[:]            # 처음 자리를 따로 복사해 둔다(start = seats 는 같은 목록에 이름만 둘)m = int(data[1 + n])pos = 2 + nfor _ in range(m):    i, j = int(data[pos]) - 1, int(data[pos + 1]) - 1    pos += 2    seats[i], seats[j] = seats[j], seats[i] now = {name: k for k, name in enumerate(seats)}moved = [(name, k + 1, now[name] + 1) for k, name in enumerate(start) if now[name] != k]print(" ".join(seats))print(len(moved))for name, a, b in moved:    print(name, a, b)
JavaScriptmain.js · 20 行
const data = require("fs").readFileSync(0, "utf8").trim().split(/\s+/);const n = Number(data[0]);const seats = data.slice(1, 1 + n);const start = [...seats]; // 복사본. const start = seats 는 같은 배열을 가리킨다const m = Number(data[1 + n]);let pos = 2 + n;for (let k = 0; k < m; k++, pos += 2) {  const i = Number(data[pos]) - 1;  const j = Number(data[pos + 1]) - 1;  [seats[i], seats[j]] = [seats[j], seats[i]];} const now = new Map(seats.map((name, k) => [name, k]));const out = [seats.join(" ")];const moved = [];start.forEach((name, k) => {  if (now.get(name) !== k) moved.push(`${name} ${k + 1} ${now.get(name) + 1}`);});out.push(String(moved.length), ...moved);console.log(out.join("\n"));
TypeScriptmain.ts · 22 行
import { readFileSync } from "node:fs";const data: string[] = readFileSync(0, "utf8").trim().split(/\s+/);const n = Number(data[0]);const seats: string[] = data.slice(1, 1 + n);const start: string[] = [...seats]; // 복사본. const start = seats 는 같은 배열을 가리킨다const m = Number(data[1 + n]);let pos = 2 + n;for (let k = 0; k < m; k++, pos += 2) {  const i = Number(data[pos]) - 1;  const j = Number(data[pos + 1]) - 1;  [seats[i], seats[j]] = [seats[j], seats[i]];} const now = new Map<string, number>(seats.map((name, k): [string, number] => [name, k]));const out: string[] = [seats.join(" ")];const moved: string[] = [];start.forEach((name, k) => {  const at = now.get(name)!;  if (at !== k) moved.push(`${name} ${k + 1} ${at + 1}`);});out.push(String(moved.length), ...moved);console.log(out.join("\n"));
JavaMain.java · 33 行
import java.io.*;import java.util.*; public class Main {    public static void main(String[] args) throws IOException {        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));        int n = Integer.parseInt(br.readLine().trim());        String[] seats = br.readLine().trim().split(" ");        String[] start = seats.clone(); // String[] start = seats; 는 같은 배열을 가리킨다        int m = Integer.parseInt(br.readLine().trim());        for (int k = 0; k < m; k++) {            StringTokenizer st = new StringTokenizer(br.readLine());            int i = Integer.parseInt(st.nextToken()) - 1;            int j = Integer.parseInt(st.nextToken()) - 1;            String tmp = seats[i];            seats[i] = seats[j];            seats[j] = tmp;        }         Map<String, Integer> now = new HashMap<>();        for (int k = 0; k < n; k++) now.put(seats[k], k);        StringBuilder moved = new StringBuilder();        int count = 0;        for (int k = 0; k < n; k++) {            int at = now.get(start[k]);            if (at != k) {                count++;                moved.append(start[k]).append(' ').append(k + 1).append(' ').append(at + 1).append('\n');            }        }        System.out.print(String.join(" ", seats) + "\n" + count + "\n" + moved);    }}
C#Main.cs · 33 行
using System;using System.Collections.Generic;using System.Text; class Program{    static void Main()    {        int n = int.Parse(Console.ReadLine().Trim());        string[] seats = Console.ReadLine().Trim().Split(' ');        string[] start = (string[])seats.Clone(); // string[] start = seats; 는 같은 배열을 가리킨다        int m = int.Parse(Console.ReadLine().Trim());        for (int k = 0; k < m; k++)        {            string[] p = Console.ReadLine().Trim().Split(' ');            int i = int.Parse(p[0]) - 1, j = int.Parse(p[1]) - 1;            (seats[i], seats[j]) = (seats[j], seats[i]);        }         var now = new Dictionary<string, int>();        for (int k = 0; k < n; k++) now[seats[k]] = k;        var moved = new List<string>();        for (int k = 0; k < n; k++)        {            int at = now[start[k]];            if (at != k) moved.Add($"{start[k]} {k + 1} {at + 1}");        }        var sb = new StringBuilder();        sb.Append(string.Join(" ", seats)).Append('\n').Append(moved.Count).Append('\n');        foreach (string line in moved) sb.Append(line).Append('\n');        Console.Write(sb);    }}
C++main.cpp · 33 行
#include <iostream>#include <string>#include <unordered_map>#include <utility>#include <vector> int main() {    int n, m;    std::cin >> n;    std::vector<std::string> seats(n);    for (auto& s : seats) std::cin >> s;    std::vector<std::string> start = seats; // vector는 = 가 통째로 복사한다(참조가 아니다)    std::cin >> m;    for (int k = 0; k < m; k++) {        int i, j;        std::cin >> i >> j;        std::swap(seats[i - 1], seats[j - 1]);    }     std::unordered_map<std::string, int> now;    for (int k = 0; k < n; k++) now[seats[k]] = k;    std::string out, moved;    int count = 0;    for (int k = 0; k < n; k++) out += (k ? " " : "") + seats[k];    for (int k = 0; k < n; k++) {        int at = now[start[k]];        if (at != k) {            count++;            moved += start[k] + " " + std::to_string(k + 1) + " " + std::to_string(at + 1) + "\n";        }    }    std::cout << out << "\n" << count << "\n" << moved;}
Cmain.c · 37 行
#include <stdio.h>#include <string.h> static char seats[1000][11];static char start[1000][11]; int main(void) {    int n, m;    scanf("%d", &n);    for (int k = 0; k < n; k++) scanf("%10s", seats[k]);    memcpy(start, seats, sizeof seats); /* 배열은 = 로 복사할 수 없다: 칸을 통째로 복사 */    scanf("%d", &m);    for (int k = 0; k < m; k++) {        int i, j;        char tmp[11];        scanf("%d %d", &i, &j);        i--, j--;        if (i == j) continue; /* 같은 칸끼리 strcpy 하면 겹친 복사라 안 된다 */        strcpy(tmp, seats[i]);        strcpy(seats[i], seats[j]);        strcpy(seats[j], tmp);    }     /* 처음 자리마다 지금 자리를 찾는다(n이 1000 이하라 차례로 찾아도 된다) */    static int at[1000];    int count = 0;    for (int k = 0; k < n; k++) {        for (int t = 0; t < n; t++)            if (strcmp(seats[t], start[k]) == 0) { at[k] = t; break; }        if (at[k] != k) count++;    }    for (int k = 0; k < n; k++) printf(k ? " %s" : "%s", seats[k]);    printf("\n%d\n", count);    for (int k = 0; k < n; k++)        if (at[k] != k) printf("%s %d %d\n", start[k], k + 1, at[k] + 1);    return 0;}
Craykonmain.cray · 35 行
n = コンソール.行読み().数に();seats = コンソール.行読み().空白除去().分ける();// start = seats; 라면 같은 목록에 이름만 둘이다. 부분목록은 새 목록을 만든다start = seats.部分リスト(0, seats.個数);m = コンソール.行読み().数に();繰り返す (k = 0; k < m; k++){    p = コンソール.数読み();    i = p[0] - 1;    j = p[1] - 1;    tmp = seats[i];    seats[i] = seats[j];    seats[j] = tmp;} now = 辞書();繰り返す (k = 0; k < n; k++){    now[seats[k]] = k;}moved = [];繰り返す (k = 0; k < n; k++){    at = now[start[k]];    もし (at != k)    {        moved.追加(start[k] + " " + (k + 1) + " " + (at + 1));    }}コンソール.書く(seats.つなぐ(" "));コンソール.書く(moved.個数);それぞれ (line の中 moved){    コンソール.書く(line);}