{ }codelper
値型と参照型参照レコードP0159

複製された冒険者と共有の金庫

冒険者が n 人、チームが t 個ある。
冒険者はそれぞれ座標 (x, y) を持ち、一つのチームに属する。
チームごとに金庫が一つあり、同じチームの冒険者はみなその一つの金庫を共有する。
一行目に n と t、二行目に 1 番から t 番のチームの最初の金額 t 個が与えられる。
続く n 行に 1 番から n 番の冒険者が「x y チーム番号」で与えられる。
続いて命令数 q、続く q 行に命令が一つずつ与えられる。
- move i dx dy:i 番の冒険者が x 方向に dx、y 方向に dy だけ動く。
- earn i g:i 番の冒険者が属するチームの金庫に g を入れる。
- clone i j:i 番の冒険者を j 番の冒険者の複製にする。
座標は j のいまの座標と同じになり、チームは j のチームになる。
そのあと二人の座標は別々に動くが、同じチームなので金庫は共有する。
- leave i:i 番の冒険者がいまのチームを離れ、金庫が 0 の新しいチームを一人で作る。
元のチームの金庫はそのまま残り、いまのチームに一人だけだったとしても新しいチームの金庫は 0 である。
i と j は同じこともある(そのとき clone は何も変えない)。
命令を順に終えたあと、1 番から n 番の冒険者ごとに「x y 金庫の金額」を一行ずつ出力せよ。
金庫の金額はその冒険者が属するチームの金庫に入っている金額である。
冒険者を、座標の構造体(値)とチームを指すもの(C のポインタ、C++ の shared_ptr、C# のクラス参照)をメンバーに持つ構造体にし、clone を構造体の代入一回で解いてみよう。

入力
1 ≤ n ≤ 1,000、1 ≤ t ≤ 1,000、1 ≤ q ≤ 10,000。
最初の金額は 0 以上 1,000,000 以下、g は 1 以上 1,000 以下、最初の座標と dx・dy は -1,000 以上 1,000 以下の整数。
1 ≤ チーム番号 ≤ t、1 ≤ i, j ≤ n
出力
n 行:冒険者ごとに「x y 金庫の金額」
例 1 · stdin
3 2
10 20
0 0 1
5 5 1
9 9 2
5
earn 1 3
clone 3 1
move 3 1 1
earn 3 100
leave 2
stdout
0 0 113
5 5 0
1 1 113
main.py
入力(stdin)

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

$ 準備完了

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

ほかの言語では?言語別の解答を見る · 3 言語の解答

この問題は C・C++・C# だけを受け付けます。
代入すると丸ごとコピーされる値型の構造体の中に、別のものを指すメンバーを一緒に置けるのはこの三つです。
Python・JavaScript・TypeScript・Java のオブジェクトと Craykon の 辞書()はすべて参照なので、「座標はコピー、チームは共有」を代入一回で分けられません。
要は、構造体の代入が浅いコピーだという点です。
値のメンバー(座標)は新しくコピーされ、指すメンバーはアドレス(参照)だけがコピーされて同じものを一緒に指します。
C は Team *team、C++ は std::shared_ptr<Team> team(コピーすると同じ Team を一緒に指し、最後の一つが消えるときに削除されます)、C# は struct Adventurer の中の class Team フィールドがその役目です。
落とし穴は五つ:① C# で Point を class にすると、clone のあと二人が一つの座標を共有し、片方が動くと両方動きます。
② C# で Team を struct にすると、clone のとき金庫がコピーされ、そのあと入れたお金が片方にしか入りません。
③ C# で Adventurer を class にすると、a[i] = a[j] が二つのマスを一つのオブジェクトにします。
④ C・C++ でチームを Team team; のように値で持つと、最初から同じチームの冒険者どうしでも金庫が別々になります。
⑤ C++ で Adventurer me = a[i - 1]; と取り出すとコピーだけが変わります。
Adventurer &me で受けます。
C# も List<Adventurer> だと list[i].Pos.X += dx がコンパイルエラー(CS1612)になるので、マスが変数である配列 Adventurer[] を使います。

C#Main.cs · 67 行
using System;using System.Text; struct Point   // 값 형식: 대입하면 X, Y가 복사된다{    public int X, Y;} class Team     // 참조 형식: 대입하면 같은 금고를 함께 가리킨다{    public int Gold;} struct Adventurer  // 값 형식 안에 값(Pos)과 참조(Team)가 함께 있다{    public Point Pos;    public Team Team;} class Program{    static void Main()    {        var tokens = Console.In.ReadToEnd().Split((char[]?)null, StringSplitOptions.RemoveEmptyEntries);        int p = 0;        int Next() => int.Parse(tokens[p++]);         int n = Next(), t = Next();        var teams = new Team[t];        for (int k = 0; k < t; k++) teams[k] = new Team { Gold = Next() };         var a = new Adventurer[n];  // List<Adventurer>가 아니라 배열: a[i].Pos.X += dx가 칸 자체를 바꾼다        for (int i = 0; i < n; i++)        {            a[i].Pos.X = Next();            a[i].Pos.Y = Next();            a[i].Team = teams[Next() - 1];        }         int q = Next();        for (int c = 0; c < q; c++)        {            string cmd = tokens[p++];            int i = Next() - 1;            switch (cmd)            {                case "move":                    a[i].Pos.X += Next();                    a[i].Pos.Y += Next();                    break;                case "earn":                    a[i].Team.Gold += Next();                    break;                case "clone":                    a[i] = a[Next() - 1];  // Pos는 복사되고, Team은 참조만 복사된다                    break;                default:  // leave                    a[i].Team = new Team();                    break;            }        }         var sb = new StringBuilder();        foreach (var ad in a) sb.Append($"{ad.Pos.X} {ad.Pos.Y} {ad.Team.Gold}\n");        Console.Write(sb);    }}
C++main.cpp · 60 行
#include <iostream>#include <memory>#include <string>#include <vector> struct Point {  // 값: 대입하면 복사된다    int x = 0, y = 0;}; struct Team {    int gold = 0;}; // 모험가는 좌표를 직접 담고(값), 팀은 shared_ptr로 함께 가리킨다struct Adventurer {    Point pos;    std::shared_ptr<Team> team;}; int main() {    std::ios::sync_with_stdio(false);    int n, t;    std::cin >> n >> t;    std::vector<std::shared_ptr<Team>> teams(t);    for (auto &tm : teams) {        tm = std::make_shared<Team>();        std::cin >> tm->gold;    }    std::vector<Adventurer> a(n);    for (auto &ad : a) {        int k;        std::cin >> ad.pos.x >> ad.pos.y >> k;        ad.team = teams[k - 1];    }    int q;    std::cin >> q;    for (int c = 0; c < q; c++) {        std::string cmd;        int i;        std::cin >> cmd >> i;        Adventurer &me = a[i - 1];  // 참조로 받아야 배열의 모험가가 바뀐다        if (cmd == "move") {            int dx, dy;            std::cin >> dx >> dy;            me.pos.x += dx;            me.pos.y += dy;        } else if (cmd == "earn") {            int g;            std::cin >> g;            me.team->gold += g;        } else if (cmd == "clone") {            int j;            std::cin >> j;            me = a[j - 1];  // pos는 복사, shared_ptr는 같은 Team을 함께 가리키게 복사        } else {            me.team = std::make_shared<Team>();  // 새 팀(금고 0)        }    }    for (const auto &ad : a) std::cout << ad.pos.x << ' ' << ad.pos.y << ' ' << ad.team->gold << '\n';}
Cmain.c · 59 行
#include <stdio.h>#include <stdlib.h>#include <string.h> typedef struct { int x, y; } Point;   /* 값: 대입하면 복사된다 */typedef struct { int gold; } Team; /* 모험가는 좌표를 직접 담고(값), 팀은 주소로 가리킨다(같은 팀이면 같은 주소) */typedef struct {    Point pos;    Team *team;} Adventurer; int main(void) {    int n, t, q;    scanf("%d %d", &n, &t);    /* 팀 자리: 처음 t개 + leave 때마다 하나씩(많아야 q개) */    int cap = t + 10000;    Team *teams = malloc((size_t)cap * sizeof *teams);    int used = t;    for (int k = 0; k < t; k++) scanf("%d", &teams[k].gold);     Adventurer *a = malloc((size_t)n * sizeof *a);    for (int i = 0; i < n; i++) {        int k;        scanf("%d %d %d", &a[i].pos.x, &a[i].pos.y, &k);        a[i].team = &teams[k - 1];    }     scanf("%d", &q);    for (int c = 0; c < q; c++) {        char cmd[8];        int i;        scanf("%7s %d", cmd, &i);        Adventurer *me = &a[i - 1];        if (strcmp(cmd, "move") == 0) {            int dx, dy;            scanf("%d %d", &dx, &dy);            me->pos.x += dx;            me->pos.y += dy;        } else if (strcmp(cmd, "earn") == 0) {            int g;            scanf("%d", &g);            me->team->gold += g;          /* 같은 팀 모두가 보는 금고 */        } else if (strcmp(cmd, "clone") == 0) {            int j;            scanf("%d", &j);            *me = a[j - 1];               /* 구조체 대입: pos는 복사, team은 주소만 복사 */        } else {                          /* leave: 새 팀을 만들어 옮긴다 */            teams[used].gold = 0;            me->team = &teams[used++];        }    }     for (int i = 0; i < n; i++) printf("%d %d %d\n", a[i].pos.x, a[i].pos.y, a[i].team->gold);    free(a);    free(teams);    return 0;}