学校でペアを書いておく台帳を二冊使う。 ロッカー台帳（locker）はロッカー番号（整数）と生徒の名前をペアにし、あだ名台帳（nick）はあだ名と生徒の名前をペアにする。 ペアのうち番号やあだ名を左、名前を右と呼ぶ。 一つの台帳の中で、一つの左は多くても一つのペアにしか入っておらず、一つの右も多くても一つのペアにしか入っていない。 二つの台帳は互いに影響せず、最初はどちらも空である。 命令は「台帳 動作 [値]」の形で、台帳は locker または nick である。 - put a b：左が a のペアがあれば消し、右が b のペアがあれば消してから、a と b を新しくペアにする。 - get a：左が a のペアの右を出力する。 そのようなペアがなければ - を出力する。 - find b：右が b のペアの左を出力する。 そのようなペアがなければ - を出力する。 - del a：左が a のペアがあれば消す。 - drop b：右が b のペアがあれば消す。 - size：その台帳にあるペアの数を出力する。 一行目に命令の数 q、続く q 行に命令が一つずつ与えられる。 get、find、size ごとに一行ずつ出力せよ。 左の型 K と右の型 V をパラメータとして受け取るジェネリッククラス（C++ はクラステンプレート）BiMap<K, V> を一つだけ作り、二つの台帳をどちらもそのクラスで作って解いてみよう。 同じペアを逆向きに見る台帳を返すメソッド inverse() も作ってみよう。 その型は BiMap<V, K> である。
18
locker put 7 ann
locker put 0 bo
nick put ace ann
locker get 7
locker put 7 bo
locker find ann
locker find bo
locker get 0
locker size
locker put 0 cy
locker find cy
locker get 3
locker find dan
locker size
nick find ann
nick drop ann
nick get ace
nick size
stdout
ann
-
7
-
1
0
-
-
2
ace
-
0
main.py
エラー一覧00F8 ↓ · ⇧F8 ↑
入力(stdin)
実行すると、これらの行が順に input()・標準入力に渡されます(実行中に入力を求めません)。
$ 準備完了
コードを入力して解くにはパソコンで開いてください。モバイルでは問題と解答を見られます。
ほかの言語では？言語別の解答を見る · 4 言語の解答
この問題はジェネリクスがある TypeScript・Java・C#・C++ だけを受け付けます（C++ はクラステンプレート）。 Python・JavaScript は型を書かないので一つのクラスが最初から何でも入れられ（Python の Generic[K, V] は書いておくだけで実行時には検査しません）、C と Craykon には型パラメータがありません。 BiMap<K, V> は二つの辞書（K→V、V→K）を一緒に直します。 inverse() はその二つの辞書を入れ替えて持つ BiMap<V, K> を返すので、find b は inverse().get(b)、drop b は inverse().remove(b) になります。 型パラメータが二つあり、その位置が入れ替わることが要点です。 型引数の書き方は TS BiMap.create<number, string>()、Java new BiMap<Integer, String>()、C# new BiMap<int, string>()、C++ BiMap<int, string> です。 Java は BiMap<int, String> と書くとコンパイルエラー（unexpected type）なので、Integer で持ちます。 左の型だけが違う二つの台帳はジェネリック関数 run<K> 一つで処理し、文字列を K に変える関数も一緒に渡します。 「ない」を返す方法は言語ごとに違います。 TS は V | undefined、Java は null、C# は bool TryGet(K k, out V v)、C++ は optional<V> を使いました。 罠その一：put が古いペアを消さないと、古いペアが残ります。 例の locker put 7 bo の後で locker find ann が 7、locker get 0 が bo、locker size が 2 になります。 罠その二：TS で「ない」を x ? String(x) : "-" で見分けると数 0 も偽なので、例の locker find cy が 0 ではなく - になります。 x === undefined で尋ねます。 罠その三：C# でなければ default(V) を返して null かどうかで見分けると、V が int のとき default は 0 です。 例の locker find ann と locker find dan が 0 になり、本当の 0 番ロッカーと区別できません。 罠その四：Java は get が返した null を String.valueOf で文字列に入れると、- の代わりに null と出ます。 罠その五：C++ の map の operator[] で探すと、ないキーが既定値と一緒に辞書に作られます。 既定値なら「ない」と見る解答は、例で locker size が 2 と 3 に増え、locker find cy も - になります。 find で探します。
TypeScriptmain.ts · 68 行
import { readFileSync } from "node:fs";// 왼쪽 K와 오른쪽 V를 하나씩 짝짓는 두 방향 사전class BiMap<K, V> { private constructor( private readonly fwd: Map<K, V>, private readonly rev: Map<V, K>, ) {} static create<K, V>(): BiMap<K, V> { return new BiMap<K, V>(new Map<K, V>(), new Map<V, K>()); } // 같은 짝들을 거꾸로 보는 사전: 타입 인자의 자리가 바뀐다 inverse(): BiMap<V, K> { return new BiMap<V, K>(this.rev, this.fwd); } get(k: K): V | undefined { return this.fwd.get(k); } remove(k: K): void { const v = this.fwd.get(k); if (v === undefined) return; this.fwd.delete(k); this.rev.delete(v); } put(k: K, v: V): void { this.remove(k); this.inverse().remove(v); this.fwd.set(k, v); this.rev.set(v, k); } get size(): number { return this.fwd.size; }}function show<T>(x: T | undefined): string { return x === undefined ? "-" : String(x);}const out: string[] = [];// 왼쪽 타입 K만 다른 두 장부를 같은 코드로 처리한다function run<K>(m: BiMap<K, string>, parse: (s: string) => K, p: string[]): void { const cmd = p[1]; if (cmd === "put") m.put(parse(p[2]), p[3]); else if (cmd === "get") out.push(show(m.get(parse(p[2])))); else if (cmd === "find") out.push(show(m.inverse().get(p[2]))); else if (cmd === "del") m.remove(parse(p[2])); else if (cmd === "drop") m.inverse().remove(p[2]); else out.push(String(m.size));}const lines: string[] = readFileSync(0, "utf8").split("\n");const q = Number(lines[0]);const locker = BiMap.create<number, string>();const nick = BiMap.create<string, string>();for (let i = 1; i <= q; i++) { const p = lines[i].trim().split(/\s+/); if (p[0] === "locker") run(locker, Number, p); else run(nick, (s) => s, p);}console.log(out.join("\n"));
JavaMain.java · 67 行
import java.io.*;import java.util.*;import java.util.function.Function;// 왼쪽 K와 오른쪽 V를 하나씩 짝짓는 두 방향 사전class BiMap<K, V> { private final Map<K, V> fwd; private final Map<V, K> rev; BiMap() { this(new HashMap<>(), new HashMap<>()); } private BiMap(Map<K, V> fwd, Map<V, K> rev) { this.fwd = fwd; this.rev = rev; } // 같은 짝들을 거꾸로 보는 사전: 타입 인자의 자리가 바뀐다 BiMap<V, K> inverse() { return new BiMap<>(rev, fwd); } // 없으면 null V get(K k) { return fwd.get(k); } void remove(K k) { V v = fwd.remove(k); if (v != null) rev.remove(v); } void put(K k, V v) { remove(k); inverse().remove(v); fwd.put(k, v); rev.put(v, k); } int size() { return fwd.size(); }}public class Main { static StringBuilder sb = new StringBuilder(); static <T> String show(T x) { return x == null ? "-" : x.toString(); } // 왼쪽 타입 K만 다른 두 장부를 같은 코드로 처리한다 static <K> void run(BiMap<K, String> m, Function<String, K> parse, String[] p) { switch (p[1]) { case "put": m.put(parse.apply(p[2]), p[3]); break; case "get": sb.append(show(m.get(parse.apply(p[2])))).append('\n'); break; case "find": sb.append(show(m.inverse().get(p[2]))).append('\n'); break; case "del": m.remove(parse.apply(p[2])); break; case "drop": m.inverse().remove(p[2]); break; default: sb.append(m.size()).append('\n'); } } public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); int q = Integer.parseInt(br.readLine().trim()); BiMap<Integer, String> locker = new BiMap<>(); // int는 타입 인자가 될 수 없어 Integer로 담는다 BiMap<String, String> nick = new BiMap<>(); for (int i = 0; i < q; i++) { String[] p = br.readLine().trim().split(" "); if (p[0].equals("locker")) run(locker, Integer::valueOf, p); else run(nick, s -> s, p); } System.out.print(sb); }}
C#Main.cs · 79 行
using System;using System.Collections.Generic;using System.Text;// 왼쪽 K와 오른쪽 V를 하나씩 짝짓는 두 방향 사전class BiMap<K, V>{ private readonly Dictionary<K, V> fwd; private readonly Dictionary<V, K> rev; public BiMap() : this(new Dictionary<K, V>(), new Dictionary<V, K>()) { } private BiMap(Dictionary<K, V> fwd, Dictionary<V, K> rev) { this.fwd = fwd; this.rev = rev; } // 같은 짝들을 거꾸로 보는 사전: 타입 인자의 자리가 바뀐다 public BiMap<V, K> Inverse() => new BiMap<V, K>(rev, fwd); // 있는지 없는지를 bool로 돌려주고, 값은 out으로 내보낸다 public bool TryGet(K k, out V v) => fwd.TryGetValue(k, out v); public void Remove(K k) { if (fwd.Remove(k, out V v)) rev.Remove(v); } public void Put(K k, V v) { Remove(k); Inverse().Remove(v); fwd[k] = v; rev[v] = k; } public int Count => fwd.Count;}class Program{ static readonly StringBuilder sb = new StringBuilder(); // 왼쪽 타입 K만 다른 두 장부를 같은 코드로 처리한다 static void Run<K>(BiMap<K, string> m, Func<string, K> parse, string[] p) { switch (p[1]) { case "put": m.Put(parse(p[2]), p[3]); break; case "get": if (m.TryGet(parse(p[2]), out string name)) sb.Append(name); else sb.Append('-'); sb.Append('\n'); break; case "find": if (m.Inverse().TryGet(p[2], out K left)) sb.Append(left); else sb.Append('-'); sb.Append('\n'); break; case "del": m.Remove(parse(p[2])); break; case "drop": m.Inverse().Remove(p[2]); break; default: sb.Append(m.Count).Append('\n'); break; } } static void Main() { var lines = Console.In.ReadToEnd().Split('\n'); int q = int.Parse(lines[0].Trim()); var locker = new BiMap<int, string>(); // int를 포장 없이 그대로 담는다 var nick = new BiMap<string, string>(); for (int i = 1; i <= q; i++) { var p = lines[i].Trim().Split(' '); if (p[0] == "locker") Run(locker, int.Parse, p); else Run(nick, s => s, p); } Console.Write(sb); }}
C++main.cpp · 89 行
#include <iostream>#include <map>#include <memory>#include <optional>#include <string>using namespace std;// 왼쪽 K와 오른쪽 V를 하나씩 짝짓는 두 방향 사전template <class K, class V>class BiMap { shared_ptr<map<K, V>> fwd_; shared_ptr<map<V, K>> rev_;public: BiMap() : fwd_(make_shared<map<K, V>>()), rev_(make_shared<map<V, K>>()) {} BiMap(shared_ptr<map<K, V>> fwd, shared_ptr<map<V, K>> rev) : fwd_(std::move(fwd)), rev_(std::move(rev)) {} // 같은 짝들을 거꾸로 보는 사전: 타입 인자의 자리가 바뀐다 BiMap<V, K> inverse() const { return BiMap<V, K>(rev_, fwd_); } // find는 없는 키를 만들지 않는다 optional<V> get(const K& k) const { auto it = fwd_->find(k); if (it == fwd_->end()) return nullopt; return it->second; } void remove(const K& k) { auto it = fwd_->find(k); if (it == fwd_->end()) return; rev_->erase(it->second); fwd_->erase(it); } void put(const K& k, const V& v) { remove(k); inverse().remove(v); (*fwd_)[k] = v; (*rev_)[v] = k; } size_t size() const { return fwd_->size(); }};template <class T>void show(const optional<T>& x) { if (x) cout << *x << '\n'; else cout << "-\n";}// 왼쪽 타입 K만 다른 두 장부를 같은 코드로 처리한다template <class K, class Parse>void run(BiMap<K, string>& m, Parse parse, const string& cmd) { string a, b; if (cmd == "put") { cin >> a >> b; m.put(parse(a), b); } else if (cmd == "get") { cin >> a; show(m.get(parse(a))); } else if (cmd == "find") { cin >> b; show(m.inverse().get(b)); } else if (cmd == "del") { cin >> a; m.remove(parse(a)); } else if (cmd == "drop") { cin >> b; m.inverse().remove(b); } else { cout << m.size() << '\n'; }}int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int q; cin >> q; BiMap<int, string> locker; BiMap<string, string> nick; for (int i = 0; i < q; i++) { string ledger, cmd; cin >> ledger >> cmd; if (ledger == "locker") run(locker, [](const string& s) { return stoi(s); }, cmd); else run(nick, [](const string& s) { return s; }, cmd); } return 0;}