Javaの解答例：学習記録：C - Colorful Beans , トヨタ自動車プログラミングコンテスト2024#4（AtCoder Beginner Contest 348）

はじめに

この問題のポイント

• 愚直にやると、メモリの制限と制限時間に間に合わなくなるかも。
• 配列を用意する時にもメモリの要領を確保しないといけないからね。小さいなら問題ないけど、大きいならちょっと。キャリーケースに分厚いニットを入れるとほかの者がいれられないのに似ている。
• だから、連想配列を使うよ。
• 最小値の最大化は二分探索を使うらしい。
• 解法が分かっていただけに悔しかった問題。でも実装できないんですよねー。
• これをきっかけに連想配列の使い方をマスターしよう！

目次

問題と解説

問題 atcoder.jp

解説 atcoder.jp

YouTube youtu.be

解答例

公式の解答を私なりに、Javaに変換

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        int[] a = new int[N];
        int[] c = new int[N];

        Map<Integer, Integer> mininumTaste = new HashMap<Integer, Integer>();


        for (int i = 0; i < N; i++) {
            a[i] = sc.nextInt();
            c[i] = sc.nextInt();
        }

        for (int i = 0; i < N; i++) {
            if (mininumTaste.containsKey(c[i])) {
                mininumTaste.put(c[i], Math.min(mininumTaste.get(c[i]), a[i]));
            } else {
                mininumTaste.put(c[i], a[i]);
            }
        }

        int ans = -1;
        for (int i : mininumTaste.keySet()) {
            ans = Math.max(ans, mininumTaste.get(i));
        }

        System.out.println(ans);

        sc.close();
    }
}

ほかの解答例

なるほど、解法の部分をsolve()としてmain()の外に出しているのですね。参考になります。

atcoder.jp

import java.util.*;
import java.io.*;

public class Main {
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();

        int[] a = new int[n];
        int[] c = new int[n];
        for (int i = 0; i < n; i++) {
            a[i] = sc.nextInt();
            c[i] = sc.nextInt();
        }

        System.out.println(solve(n, a, c));
    }

    static String solve(int n, int[] a, int[] c) {
        HashMap<Integer, Integer> cmin = new HashMap<>();
        for(int i=0; i<n; i++) {
            cmin.put(c[i], Math.min(a[i], cmin.getOrDefault(c[i], Integer.MAX_VALUE)));
        }
        int result = 0;
        for(Integer ai: cmin.values()) {
            result = Math.max(result, ai);
        }

        return String.valueOf(result).trim();
    }
}

所感

ほかの人のコードを見るの面白いですね！ なんか、こう、めちゃくちゃ長いのから、普通にきれいなものまでたくさんありますね。あと、テクニック満載なものもあって、見ていて面白い。