{ }codelper
インターフェースジェネリクスP0081

ひとつで使う最大値

面積を持つ図形インターフェースを作り、長方形クラスと直角三角形クラスにそれを実装させよ。
そしてリストから最大のものを探すジェネリック関数を一つ作り、整数のリスト、単語のリスト、図形のリストのすべてに使え。
最大のものが複数あれば、リストでいちばん前のものを選ぶ。
入力は五つの部分からなる:整数の個数 n、整数 n 個(一行)、単語の個数 m、単語 m 個(一行)、図形の個数 k、そして図形 k 行。
図形の行は "rect w h"(横 w、縦 h の長方形、面積 w × h)または "tri b h"(底辺 b、高さ h の直角三角形、面積 b × h ÷ 2)である。
三行を出力せよ:最大の整数、辞書順でいちばん後ろに来る単語、そして面積が最大の図形の "番号 図形の行"(番号は 1 から数えた入力の順、図形の行は入力のまま)。

入力
1 ≤ n, m, k ≤ 1000。
-1,000,000,000 ≤ 整数 ≤ 1,000,000,000。
単語は英小文字 1〜10 文字。
1 ≤ w, h, b ≤ 10,000(整数)
出力
三行
例 1 · stdin
4
9 10 -3 10
3
banana apple cherry
3
rect 2 2
tri 3 3
tri 9 1
stdout
10
cherry
2 tri 3 3
main.py
入力(stdin)

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

$ 準備完了

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

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

この問題はインターフェースとジェネリクスのある TypeScript・Java・C# だけを受け付けます(Python・JS は型を書かないのでジェネリクスが別になく、C にはどちらもありません。
C++ のテンプレートは形がかなり違うので、この問題では外しました)。
三つの言語は「互いに比べられる T」を違う言い方で書きます。
Java <T extends Comparable<? super T>>、C# where T : IComparable<T> のように型に制約をかけ、図形インターフェースが Comparable<Shape>・IComparable<IShape> を受け継いで面積で比べる方法を一度だけ決めます(Java の default メソッド、C# 8 のインターフェースの既定の実装)。
Java は List<int> が使えないので List<Integer> に入れます。
TS は数と文字列に比較メソッドがないので、argMax<T>(items: T[], compare: (a: T, b: T) => number) のように比較関数を一緒に受け取るのが自然です。
落とし穴:TS で数を Number() で変換せず文字列のまま < で比べると "9" > "10" のように文字列の順になります(型を T にしておくとコンパイラも見つけられません)。
三角形の面積を整数の割り算 b * h / 2 で求めると 4.5 が 4 に切り捨てられ、面積 4 の長方形と同じになります。
面積の二倍 b * h で比べれば整数だけで数えられます。
同じ面積のとき前のものを選ぶには > 0 のときだけ入れ替え、>= 0 だと最後のものを選びます。
C# の string の CompareTo はカルチャの規則で比べますが(純粋なコード順は string.CompareOrdinal)、この問題は小文字だけなので結果は同じです。

TypeScriptmain.ts · 45 行
import { readFileSync } from "node:fs"; interface Shape {  twiceArea(): number; // 넓이의 두 배(삼각형도 정수로 비교하려고)  describe(): string;} class Rect implements Shape {  private w: number;  private h: number;  constructor(w: number, h: number) { this.w = w; this.h = h; }  twiceArea(): number { return 2 * this.w * this.h; }  describe(): string { return `rect ${this.w} ${this.h}`; }} class Tri implements Shape {  private b: number;  private h: number;  constructor(b: number, h: number) { this.b = b; this.h = h; }  twiceArea(): number { return this.b * this.h; }  describe(): string { return `tri ${this.b} ${this.h}`; }} // 가장 큰 것의 자리(같으면 앞의 것). T가 무엇이든 비교 방법만 받으면 된다function argMax<T>(items: T[], compare: (a: T, b: T) => number): number {  let best = 0;  for (let i = 1; i < items.length; i++) if (compare(items[i], items[best]) > 0) best = i;  return best;} const lines: string[] = readFileSync(0, "utf8").split("\n");const nums: number[] = lines[1].trim().split(" ").map(Number);const words: string[] = lines[3].trim().split(" ");const k: number = Number(lines[4]);const shapes: Shape[] = [];for (let i = 0; i < k; i++) {  const [kind, a, b] = lines[5 + i].trim().split(" ");  shapes.push(kind === "rect" ? new Rect(Number(a), Number(b)) : new Tri(Number(a), Number(b)));} const byOrder = <T>(a: T, b: T): number => (a < b ? -1 : a > b ? 1 : 0);console.log(nums[argMax(nums, (a, b) => a - b)]);console.log(words[argMax(words, byOrder)]);const s = argMax(shapes, (a, b) => a.twiceArea() - b.twiceArea());console.log(`${s + 1} ${shapes[s].describe()}`);
JavaMain.java · 58 行
import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;import java.util.ArrayList;import java.util.List; interface Shape extends Comparable<Shape> {    int twiceArea(); // 넓이의 두 배(삼각형도 정수로 비교하려고)    String describe();     // 넓이로 비교하는 법을 인터페이스가 한 번만 정한다    default int compareTo(Shape other) { return Integer.compare(twiceArea(), other.twiceArea()); }} class Rect implements Shape {    private final int w, h;    Rect(int w, int h) { this.w = w; this.h = h; }    public int twiceArea() { return 2 * w * h; }    public String describe() { return "rect " + w + " " + h; }} class Tri implements Shape {    private final int b, h;    Tri(int b, int h) { this.b = b; this.h = h; }    public int twiceArea() { return b * h; }    public String describe() { return "tri " + b + " " + h; }} public class Main {    /** 가장 큰 것의 자리(같으면 앞의 것). 서로 비교할 수 있는 T라면 무엇이든. */    static <T extends Comparable<? super T>> int argMax(List<T> items) {        int best = 0;        for (int i = 1; i < items.size(); i++)            if (items.get(i).compareTo(items.get(best)) > 0) best = i;        return best;    }     public static void main(String[] args) throws IOException {        BufferedReader in = new BufferedReader(new InputStreamReader(System.in));        in.readLine();        List<Integer> nums = new ArrayList<>(); // List<int>는 안 된다        for (String t : in.readLine().trim().split(" ")) nums.add(Integer.parseInt(t));        in.readLine();        List<String> words = List.of(in.readLine().trim().split(" "));        int k = Integer.parseInt(in.readLine().trim());        List<Shape> shapes = new ArrayList<>();        for (int i = 0; i < k; i++) {            String[] p = in.readLine().trim().split(" ");            int a = Integer.parseInt(p[1]), b = Integer.parseInt(p[2]);            shapes.add(p[0].equals("rect") ? new Rect(a, b) : new Tri(a, b));        }         System.out.println(nums.get(argMax(nums)));        System.out.println(words.get(argMax(words)));        int s = argMax(shapes);        System.out.println((s + 1) + " " + shapes.get(s).describe());    }}
C#Main.cs · 61 行
using System;using System.Collections.Generic;using System.Linq; interface IShape : IComparable<IShape>{    int TwiceArea(); // 넓이의 두 배(삼각형도 정수로 비교하려고)    string Describe();     // 넓이로 비교하는 법을 인터페이스가 한 번만 정한다(C# 8의 기본 구현)    int IComparable<IShape>.CompareTo(IShape other) => TwiceArea().CompareTo(other.TwiceArea());} class Rect : IShape{    private readonly int w, h;    public Rect(int w, int h) { this.w = w; this.h = h; }    public int TwiceArea() => 2 * w * h;    public string Describe() => $"rect {w} {h}";} class Tri : IShape{    private readonly int b, h;    public Tri(int b, int h) { this.b = b; this.h = h; }    public int TwiceArea() => b * h;    public string Describe() => $"tri {b} {h}";} class Program{    // 가장 큰 것의 자리(같으면 앞의 것). 서로 비교할 수 있는 T라면 무엇이든    static int ArgMax<T>(List<T> items) where T : IComparable<T>    {        int best = 0;        for (int i = 1; i < items.Count; i++)            if (items[i].CompareTo(items[best]) > 0) best = i;        return best;    }     static void Main()    {        Console.ReadLine();        var nums = Console.ReadLine().Trim().Split(' ').Select(int.Parse).ToList();        Console.ReadLine();        var words = Console.ReadLine().Trim().Split(' ').ToList();        int k = int.Parse(Console.ReadLine());        var shapes = new List<IShape>();        for (int i = 0; i < k; i++)        {            string[] p = Console.ReadLine().Trim().Split(' ');            int a = int.Parse(p[1]), b = int.Parse(p[2]);            shapes.Add(p[0] == "rect" ? new Rect(a, b) : new Tri(a, b));        }         Console.WriteLine(nums[ArgMax(nums)]);        Console.WriteLine(words[ArgMax(words)]);        int s = ArgMax(shapes);        Console.WriteLine($"{s + 1} {shapes[s].Describe()}");    }}