{ }codelper
クエリ式(LINQ・ストリーム)P0263

フリマの検索窓

フリマに品物が n 個出ていて、検索の質問 q 個に順に答える。
品物ごとに名前、種類、値段がある。
質問「種類 上限価格 k」は、その種類で値段が上限価格以下の品物を選べという意味である。
種類が * なら種類に関係なくすべての品物から選ぶ。
質問ごとに一行に、選んだ品物の数 c を先に書き、続けて選んだ品物のうち前から k 個の名前を空白一つずつ区切って出力せよ。
選んだ品物は値段の安いものが前で、値段が同じなら名前の辞書順(文字コード順なので数字が英小文字より前、ab は abc より前)で前になる。
c が k より小さければ c 個すべてを書き、c が 0 なら 0 だけを出力する。
値段はカンマなしの数字だけで与えられ、出力も数字だけで書く。
一行目に n と q、続く n 行に品物が「名前 種類 値段」で、その次の q 行に質問が一つずつ与えられる。
ループの代わりに、絞り込み → 並べ替え → 前から k 個 → 名前だけ取り出す、とつなぐクエリ式で解いてみよう。

入力
1 ≤ n ≤ 1,000、1 ≤ q ≤ 1,000、1 ≤ k ≤ 10。
品物の名前は英小文字・数字 1~10 文字で互いに異なる。
種類は英小文字 1~10 文字(質問の種類はどの品物にもない種類のこともある)。
1 ≤ 値段、上限価格 ≤ 1,000,000,000(整数)
出力
質問ごとに一行
例 1 · stdin
6 4
lamp9 lamp 12000
bluebike bike 85000
redbike bike 85000
kidbike bike 30000
oldlamp lamp 9000
citybike bike 120000
bike 90000 2
lamp 5000 3
* 12000 5
bike 1000000000 10
stdout
3 kidbike bluebike
0
2 oldlamp lamp9
4 kidbike bluebike redbike citybike
main.py
入力(stdin)

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

$ 準備完了

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

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

この問題は、絞り込み・並べ替え・切り出し・取り出しをつなぐ道具が言語に入っている Python(リスト内包表記・sorted)・JavaScript・TypeScript(配列メソッド)・Java(ストリーム)・C#(LINQ)・C++(C++20 の std::views)だけを受け付けます。
C と Craykon には、関数を受け取って絞り込んだり変換したりするリストの道具がありません。
同じことを Python [it for it in items if ...] → sorted(key=lambda it: (it.price, it.name))[:k]、JS・TS filter → sort → slice → map、Java filter → toList() の後 sorted → limit → map、C# Where → ToList() の後 OrderBy → ThenBy → Take → Select、C++ は items | std::views::filter(...) を vector に受けて std::ranges::sort の後 std::views::take(k) と書きます。
絞り込んだ結果を個数と名前の一覧で二回使うのがこの問題の落とし穴です。
① Python の filter()・map() は一回回ると空になるイテレータなので、個数を数えるために回し切ると sorted は空のものを受け取ります。
内包表記か list(...) で受けておきます。
② Java のストリームも一回しか流せないので、ストリーム変数で count() した後にまた sorted() すると IllegalStateException になります。
toList() で受けておき、必要なときに新しく stream() します。
C# の LINQ は逆に遅延評価なので、ToList() なしで二回使うとエラーは出ませんが、使うたびに最初から絞り込み直します。
③ C# の OrderBy(...).OrderBy(...) は二つ目の OrderBy が新しい第一の基準になり、名前順に並べ直します(前の値段は名前が同じときにしか効きませんが、名前は互いに異なります)。
二番目の基準は ThenBy(Java は thenComparing)でつなぎます。
名前順は StringComparer.Ordinal を渡すと文字コード順がはっきりします。
④ JS は split が返した値段が文字列なので、Number() を忘れると "100" <= "99" が真になる辞書順の比較になります。
TypeScript は price: number の型に文字列を入れると型エラーで見つけてくれます。
⑤ 値段だけで並べ替えると、同じ値段は入力順のまま残ります。
二つの基準を一緒に渡します。
おまけに、C++ の std::views::filter は遅延ビューなのでそのままでは並べ替えられず(ランダムアクセスできない)、JS の sort はその配列をその場で変えますが、filter が新しい配列を返すので元のリストはそのままです。

Pythonmain.py · 22 行
import sysfrom collections import namedtuple Item = namedtuple("Item", "name kind price") lines = sys.stdin.read().split("\n")n, q = map(int, lines[0].split())items = []for line in lines[1 : n + 1]:    name, kind, price = line.split()    items.append(Item(name, kind, int(price))) out = []for line in lines[n + 1 : n + 1 + q]:    kind, limit, k = line.split()    limit, k = int(limit), int(k)    # 거르기: 목록 내포는 목록을 만들어 두므로 개수를 센 뒤에도 다시 쓸 수 있다    picked = [it for it in items if (kind == "*" or it.kind == kind) and it.price <= limit]    # 정렬 → 앞에서 k개 → 이름만    top = [it.name for it in sorted(picked, key=lambda it: (it.price, it.name))[:k]]    out.append(" ".join([str(len(picked))] + top))print("\n".join(out))
JavaScriptmain.js · 19 行
const lines = require("fs").readFileSync(0, "utf8").split("\n");const [n, q] = lines[0].trim().split(" ").map(Number);const items = lines.slice(1, n + 1).map((line) => {  const [name, kind, price] = line.trim().split(" ");  return { name, kind, price: Number(price) }; // Number가 없으면 가격이 문자열로 비교된다}); const byPriceThenName = (a, b) => a.price - b.price || (a.name < b.name ? -1 : a.name > b.name ? 1 : 0); const out = [];for (const line of lines.slice(n + 1, n + 1 + q)) {  const [kind, limitText, kText] = line.trim().split(" ");  const limit = Number(limitText);  const picked = items.filter((it) => (kind === "*" || it.kind === kind) && it.price <= limit);  // filter는 새 배열을 주므로 sort가 picked를 바꾸어도 items는 그대로다  const top = picked.sort(byPriceThenName).slice(0, Number(kText)).map((it) => it.name);  out.push([picked.length, ...top].join(" "));}console.log(out.join("\n"));
TypeScriptmain.ts · 26 行
import { readFileSync } from "node:fs"; interface Item {  name: string;  kind: string;  price: number;} const lines: string[] = readFileSync(0, "utf8").split("\n");const [n, q] = lines[0].trim().split(" ").map(Number);const items: Item[] = lines.slice(1, n + 1).map((line) => {  const [name, kind, price] = line.trim().split(" ");  return { name, kind, price: Number(price) }; // Item 타입이 price를 number로 요구해서 Number를 빠뜨리면 타입 오류다}); const byPriceThenName = (a: Item, b: Item): number => a.price - b.price || (a.name < b.name ? -1 : a.name > b.name ? 1 : 0); const out: string[] = [];for (const line of lines.slice(n + 1, n + 1 + q)) {  const [kind, limitText, kText] = line.trim().split(" ");  const limit = Number(limitText);  const picked: Item[] = items.filter((it) => (kind === "*" || it.kind === kind) && it.price <= limit);  const top: string[] = picked.sort(byPriceThenName).slice(0, Number(kText)).map((it) => it.name);  out.push([picked.length, ...top].join(" "));}console.log(out.join("\n"));
JavaMain.java · 40 行
import java.io.BufferedReader;import java.io.InputStreamReader;import java.util.ArrayList;import java.util.Comparator;import java.util.List;import java.util.stream.Collectors; public class Main {    record Item(String name, String kind, long price) {}     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]), q = Integer.parseInt(first[1]);        List<Item> items = new ArrayList<>();        for (int i = 0; i < n; i++) {            String[] p = in.readLine().trim().split(" ");            items.add(new Item(p[0], p[1], Long.parseLong(p[2])));        }        Comparator<Item> byPriceThenName = Comparator.comparingLong(Item::price).thenComparing(Item::name);        StringBuilder out = new StringBuilder();        for (int i = 0; i < q; i++) {            String[] p = in.readLine().trim().split(" ");            String kind = p[0];            long limit = Long.parseLong(p[1]);            int k = Integer.parseInt(p[2]);            // 스트림은 한 번만 흘려보낼 수 있다: 거른 결과를 목록으로 받아 두고 두 번 쓴다            List<Item> picked = items.stream()                    .filter(it -> (kind.equals("*") || it.kind().equals(kind)) && it.price() <= limit)                    .toList();            String top = picked.stream()                    .sorted(byPriceThenName)                    .limit(k)                    .map(it -> " " + it.name())                    .collect(Collectors.joining());            out.append(picked.size()).append(top).append('\n');        }        System.out.print(out);    }}
C#Main.cs · 37 行
using System;using System.Collections.Generic;using System.Linq;using System.Text; record Item(string Name, string Kind, long Price); class Program{    static void Main()    {        int[] first = Console.ReadLine()!.Trim().Split(' ').Select(int.Parse).ToArray();        int n = first[0], q = first[1];        List<Item> items = Enumerable.Range(0, n)            .Select(_ => Console.ReadLine()!.Trim().Split(' '))            .Select(p => new Item(p[0], p[1], long.Parse(p[2])))            .ToList();        var sb = new StringBuilder();        for (int i = 0; i < q; i++)        {            string[] p = Console.ReadLine()!.Trim().Split(' ');            string kind = p[0];            long limit = long.Parse(p[1]);            int k = int.Parse(p[2]);            List<Item> picked = items                .Where(it => (kind == "*" || it.Kind == kind) && it.Price <= limit)                .ToList(); // ToList로 한 번 계산해 둔다(그냥 두면 쓸 때마다 다시 거른다)            IEnumerable<string> top = picked                .OrderBy(it => it.Price)                .ThenBy(it => it.Name, StringComparer.Ordinal) // 두 번째 기준은 OrderBy가 아니라 ThenBy                .Take(k)                .Select(it => it.Name);            sb.Append(string.Join(" ", top.Prepend(picked.Count.ToString()))).Append('\n');        }        Console.Write(sb);    }}
C++main.cpp · 38 行
#include <algorithm>#include <iostream>#include <ranges>#include <string>#include <tuple>#include <vector> struct Item {    std::string name, kind;    long long price;}; int main() {    std::ios::sync_with_stdio(false);    int n, q;    std::cin >> n >> q;    std::vector<Item> items(n);    for (auto& it : items) std::cin >> it.name >> it.kind >> it.price;     auto byPriceThenName = [](const Item& a, const Item& b) {        return std::tie(a.price, a.name) < std::tie(b.price, b.name);    };    for (int i = 0; i < q; i++) {        std::string kind;        long long limit;        int k;        std::cin >> kind >> limit >> k;        // views::filter는 게으른 보기(view)라서 정렬할 수 없다: vector로 받아 둔다        auto view = items | std::views::filter([&](const Item& it) {                        return (kind == "*" || it.kind == kind) && it.price <= limit;                    });        std::vector<Item> picked(view.begin(), view.end());        std::ranges::sort(picked, byPriceThenName);        std::cout << picked.size();        for (const Item& it : picked | std::views::take(k)) std::cout << ' ' << it.name;        std::cout << '\n';    }}