宝探し遊びで、子ども n 人が砂場のマスを掘った。 砂場のマスは (行, 列) で表し、宝は (a, b) のマスに埋まっている。 子どもごとに、掘ったマスが掘った順に与えられる。 同じマスを何度も掘った子どももいれば、一マスも掘らなかった子どももいる。 マス (r, c) と宝の距離は |r - a| + |c - b| である。 子どもごとに一行に、名前、その子が掘った異なるマスの数、その子が掘ったマスのうち宝に最も近いマスの距離を、入力に出た順に出力せよ。 一マスも掘らなかった子どもは、距離の位置に - を書く。 その次の行に、すべての子どもが掘ったマスを通して、異なるマスの数を出力せよ。 最後の行に、丁寧な子どもの名前を入力に出た順に出力せよ。 丁寧な子どもとは、一マス以上掘り、掘ったマスがすべて宝との距離が d 以下である子どもである。 ループで一つずつ数える代わりに、重複をなくす、最小の値を選ぶ、すべてそうかを尋ねる、リストをつなげる、をつないだクエリ式の処理で解いてみよう。
入力
一行目に n、a、b、d が空白一つで区切られて与えられる。 続く n 行には各行に子どもの名前、掘ったマスの数 k、続いて掘ったマスの行と列が k 組、空白一つで区切られて与えられる。 1 ≤ n ≤ 100、1 ≤ a, b ≤ 1000、0 ≤ d ≤ 2000、0 ≤ k ≤ 50、1 ≤ r, c ≤ 1000。 名前は英小文字 1〜10 文字で、互いに異なる
4 3 3 2
ann 4 3 4 2 2 3 4 3 3
bo 2 1 1 5 5
cy 0
dee 3 2 2 2 2 2 2
stdout
ann 3 0
bo 2 4
cy 0 -
dee 1 2
5
ann dee
例 2 · stdin
2 5 5 1
zed 2 1 11 11 1
yo 1 5 7
stdout
zed 2 10
yo 1 2
3
-
main.py
エラー一覧00F8 ↓ · ⇧F8 ↑
入力(stdin)
実行すると、これらの行が順に input()・標準入力に渡されます(実行中に入力を求めません)。
$ 準備完了
コードを入力して解くにはパソコンで開いてください。モバイルでは問題と解答を見られます。
ほかの言語では？言語別の解答を見る · 6 言語の解答
この問題は、リストを絞り込んだり変換したりする道具が言語に入っている Python・JavaScript・TypeScript・Java（ストリーム）・C#（LINQ）・C++（C++20 std::ranges）だけを受け付けます。 C と Craykon には、関数を受け取って絞り込みや変換をするリストの道具がありません。 同じ仕事の名前が言語ごとに違います。 重複をなくすのは Python set(cells)、JS・TS new Set(...)、Java distinct()、C# Distinct()、C++ std::set です。 子どもごとのリストを一つにつなげるのは Python の入れ子の内包表記、JS・TS・Java の flatMap、C# の SelectMany、C++ の std::views::join です。 すべてそうかを尋ねるのは all、every、allMatch、All、std::ranges::all_of で、最小の値は min、Math.min(...)、mapToInt(...).min()、Min、std::ranges::min です。 要点は「同じマス」を何で見分けるかです。 Python のタプル、Java の record、C# の値タプル (int R, int C)、C++ の pair は値で見分けます。 JS・TS の Set はオブジェクトと配列を「同じオブジェクトか」で見分けるので、解答はマスを r + "," + c という文字列のキーに変えて入れます。 罠その一：JS でマスを [r, c] の配列のまま Set に入れると、同じマスがまとまりません。 一つ目の例が ann 4、dee 3、合計 9 になります。 Java で equals のない普通のクラスで、C# で class でマスを作っても、まったく同じ答えになります。 罠その二：キーを区切り文字なしで ${r}${c} と作ると、(1, 11) と (11, 1) がどちらも 111 です。 二つ目の例が zed 1 10 と 2 になります。 罠その三：C++ の std::unique は隣り合った同じ値しか消しません。 ソートせずに使うと、一つ目の例が ann 4 と合計 7 になります。 罠その四：「すべてそうか」は空のリストでは真です（Python all、JS every）。 掘ったマスがあるかを別に尋ねないと、一つ目の例の最後の行が ann cy dee になります。 罠その五：空のリストの最小の値は言語ごとに違います。 Python の min は ValueError、Java の getAsInt() は NoSuchElementException、C# の Min は InvalidOperationException で止まります。 JS の引数なしの Math.min() はエラーなしで Infinity なので、一つ目の例の三行目が cy 0 Infinity になります。
Pythonmain.py · 25 行
import syslines = sys.stdin.read().split("\n")n, a, b, d = map(int, lines[0].split())kids = []for i in range(1, n + 1): p = lines[i].split() nums = [int(x) for x in p[2:]] # 칸은 (행, 열) 튜플: 값이 같으면 같은 것으로 친다 kids.append((p[0], list(zip(nums[0::2], nums[1::2]))))def dist(cell): return abs(cell[0] - a) + abs(cell[1] - b)for name, cells in kids: closest = min(map(dist, cells)) if cells else "-" # 빈 것의 min은 ValueError print(name, len(set(cells)), closest)print(len({cell for _, cells in kids for cell in cells}))# all은 빈 것에 참이므로 판 칸이 있는지를 따로 묻는다careful = [name for name, cells in kids if cells and all(dist(cell) <= d for cell in cells)]print(" ".join(careful) if careful else "-")
JavaScriptmain.js · 29 行
const lines = require("fs").readFileSync(0, "utf8").split("\n");const [n, a, b, d] = lines[0].trim().split(/\s+/).map(Number);const kids = [];for (let i = 1; i <= n; i++) { const p = lines[i].trim().split(/\s+/); const nums = p.slice(2).map(Number); const cells = []; for (let j = 0; j < nums.length; j += 2) cells.push({ r: nums[j], c: nums[j + 1] }); kids.push({ name: p[0], cells });}const dist = (cell) => Math.abs(cell.r - a) + Math.abs(cell.c - b);// Set은 객체·배열을 값이 아니라 '같은 객체인가'로 가리므로 문자열 열쇠로 바꿔 넣는다const key = (cell) => cell.r + "," + cell.c;const out = kids.map((kid) => { const distinct = new Set(kid.cells.map(key)).size; const closest = kid.cells.length ? Math.min(...kid.cells.map(dist)) : "-"; // 빈 것의 Math.min은 Infinity return `${kid.name} ${distinct} ${closest}`;});out.push(String(new Set(kids.flatMap((kid) => kid.cells.map(key))).size));// every는 빈 배열에 참이므로 판 칸이 있는지를 따로 묻는다const careful = kids .filter((kid) => kid.cells.length > 0 && kid.cells.every((cell) => dist(cell) <= d)) .map((kid) => kid.name);out.push(careful.length ? careful.join(" ") : "-");console.log(out.join("\n"));
TypeScriptmain.ts · 40 行
import { readFileSync } from "node:fs";interface Cell { r: number; c: number;}interface Kid { name: string; cells: Cell[];}const lines: string[] = readFileSync(0, "utf8").split("\n");const [n, a, b, d] = lines[0].trim().split(/\s+/).map(Number);const kids: Kid[] = [];for (let i = 1; i <= n; i++) { const p = lines[i].trim().split(/\s+/); const nums = p.slice(2).map(Number); const cells: Cell[] = []; for (let j = 0; j < nums.length; j += 2) cells.push({ r: nums[j], c: nums[j + 1] }); kids.push({ name: p[0], cells });}const dist = (cell: Cell): number => Math.abs(cell.r - a) + Math.abs(cell.c - b);// Set은 객체·배열을 값이 아니라 '같은 객체인가'로 가리므로 문자열 열쇠로 바꿔 넣는다const key = (cell: Cell): string => cell.r + "," + cell.c;const out: string[] = kids.map((kid) => { const distinct = new Set(kid.cells.map(key)).size; const closest = kid.cells.length ? String(Math.min(...kid.cells.map(dist))) : "-"; // 빈 것의 Math.min은 Infinity return `${kid.name} ${distinct} ${closest}`;});out.push(String(new Set(kids.flatMap((kid) => kid.cells.map(key))).size));// every는 빈 배열에 참이므로 판 칸이 있는지를 따로 묻는다const careful: string[] = kids .filter((kid) => kid.cells.length > 0 && kid.cells.every((cell) => dist(cell) <= d)) .map((kid) => kid.name);out.push(careful.length ? careful.join(" ") : "-");console.log(out.join("\n"));
JavaMain.java · 46 行
import java.io.BufferedReader;import java.io.InputStreamReader;import java.util.ArrayList;import java.util.List;import java.util.OptionalInt;import java.util.stream.Collectors;public class Main { // record는 필드 값으로 equals·hashCode를 만들어 준다: distinct()가 값으로 가린다 record Cell(int r, int c) {} record Kid(String name, List<Cell> cells) {} public static void main(String[] args) throws Exception { BufferedReader in = new BufferedReader(new InputStreamReader(System.in)); String[] first = in.readLine().trim().split(" "); int n = Integer.parseInt(first[0]), a = Integer.parseInt(first[1]); int b = Integer.parseInt(first[2]), d = Integer.parseInt(first[3]); List<Kid> kids = new ArrayList<>(); for (int i = 0; i < n; i++) { String[] p = in.readLine().trim().split(" "); List<Cell> cells = new ArrayList<>(); for (int j = 2; j < p.length; j += 2) cells.add(new Cell(Integer.parseInt(p[j]), Integer.parseInt(p[j + 1]))); kids.add(new Kid(p[0], cells)); } StringBuilder out = new StringBuilder(); for (Kid kid : kids) { long distinct = kid.cells().stream().distinct().count(); // 빈 스트림의 min은 빈 OptionalInt다 OptionalInt closest = kid.cells().stream().mapToInt(c -> Math.abs(c.r() - a) + Math.abs(c.c() - b)).min(); out.append(kid.name()).append(' ').append(distinct).append(' ') .append(closest.isPresent() ? String.valueOf(closest.getAsInt()) : "-").append('\n'); } out.append(kids.stream().flatMap(kid -> kid.cells().stream()).distinct().count()).append('\n'); // allMatch는 빈 스트림에 참이므로 판 칸이 있는지를 따로 묻는다 String careful = kids.stream() .filter(kid -> !kid.cells().isEmpty() && kid.cells().stream().allMatch(c -> Math.abs(c.r() - a) + Math.abs(c.c() - b) <= d)) .map(Kid::name) .collect(Collectors.joining(" ")); out.append(careful.isEmpty() ? "-" : careful).append('\n'); System.out.print(out); }}
C#Main.cs · 43 行
using System;using System.Collections.Generic;using System.Linq;using System.Text;class Program{ static void Main() { var lines = Console.In.ReadToEnd().Split('\n'); var first = lines[0].Trim().Split(' ').Select(int.Parse).ToArray(); int n = first[0], a = first[1], b = first[2], d = first[3]; // 칸은 값 튜플 (R, C): 값이 같으면 같은 것으로 친다 var kids = new List<(string Name, List<(int R, int C)> Cells)>(); for (int i = 1; i <= n; i++) { var p = lines[i].Trim().Split(' '); var nums = p.Skip(2).Select(int.Parse).ToArray(); var cells = Enumerable.Range(0, nums.Length / 2).Select(j => (R: nums[2 * j], C: nums[2 * j + 1])).ToList(); kids.Add((p[0], cells)); } Func<(int R, int C), int> dist = cell => Math.Abs(cell.R - a) + Math.Abs(cell.C - b); var sb = new StringBuilder(); foreach (var kid in kids) { int distinct = kid.Cells.Distinct().Count(); // 빈 것의 Min()은 InvalidOperationException string closest = kid.Cells.Any() ? kid.Cells.Min(dist).ToString() : "-"; sb.Append($"{kid.Name} {distinct} {closest}\n"); } sb.Append(kids.SelectMany(kid => kid.Cells).Distinct().Count()).Append('\n'); // All은 빈 것에 참이므로 판 칸이 있는지를 따로 묻는다 var careful = kids.Where(kid => kid.Cells.Any() && kid.Cells.All(cell => dist(cell) <= d)) .Select(kid => kid.Name) .ToList(); sb.Append(careful.Count > 0 ? string.Join(" ", careful) : "-").Append('\n'); Console.Write(sb); }}
C++main.cpp · 55 行
#include <algorithm>#include <cstdlib>#include <iostream>#include <ranges>#include <set>#include <string>#include <utility>#include <vector>using Cell = std::pair<int, int>; // (행, 열): pair는 값으로 견준다struct Kid { std::string name; std::vector<Cell> cells;};int main() { int n, a, b, d; std::cin >> n >> a >> b >> d; std::vector<Kid> kids(n); for (Kid& kid : kids) { int k; std::cin >> kid.name >> k; kid.cells.resize(k); for (Cell& cell : kid.cells) std::cin >> cell.first >> cell.second; } auto dist = [&](const Cell& cell) { return std::abs(cell.first - a) + std::abs(cell.second - b); }; for (const Kid& kid : kids) { // set에 넣으면 같은 칸은 하나만 남는다 std::set<Cell> distinct(kid.cells.begin(), kid.cells.end()); std::cout << kid.name << ' ' << distinct.size() << ' '; // 빈 범위에는 ranges::min을 쓸 수 없다 if (kid.cells.empty()) std::cout << "-\n"; else std::cout << std::ranges::min(kid.cells | std::views::transform(dist)) << '\n'; } // 아이마다의 칸 목록을 하나로 이어 붙인다 std::set<Cell> all; for (const Cell& cell : kids | std::views::transform(&Kid::cells) | std::views::join) all.insert(cell); std::cout << all.size() << '\n'; // all_of는 빈 범위에 참이므로 판 칸이 있는지를 따로 묻는다 auto careful = kids | std::views::filter([&](const Kid& kid) { return !kid.cells.empty() && std::ranges::all_of(kid.cells, [&](const Cell& cell) { return dist(cell) <= d; }); }); bool any = false; for (const Kid& kid : careful) { std::cout << (any ? " " : "") << kid.name; any = true; } std::cout << (any ? "\n" : "-\n");}