POH! Lite Java模範解答

こちらではpaiza事務局側で作成した模範解答を掲載していす。

Java: paiza事務局作成コード Vol.3 解説ブログ版

解説ブログ: もし先輩女子エンジニアが『アルゴリズム』を図解で教えてくれるとしたら

得点:100点
通過テストケース:7/7

import java.util.HashMap;
import java.util.Iterator;
import java.util.Map;
import java.util.Map.Entry;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int M = scanner.nextInt();
        int N = scanner.nextInt();
        int[] q = new int[N];
        int[] r = new int[N];
        int min_cost = 0;
        for (int i=0; i<N; i++) {
            q[i] = scanner.nextInt();
            r[i] = scanner.nextInt();
            min_cost += r[i];
        }
        HashMap<Integer, Integer> dp = new HashMap<Integer, Integer>();
        dp.put(0, 0);
        int total_q = 0;
        int total_r = 0;
        for (int i=0; i<N; i++) {
            HashMap<Integer, Integer> dp_tmp = (HashMap<Integer, Integer>)dp.clone();
            Iterator<Entry<Integer, Integer>> iter = dp.entrySet().iterator();
            while (iter.hasNext()) {
                Map.Entry<Integer, Integer> entry = iter.next();
                total_q = entry.getKey() + q[i];
                total_r = entry.getValue() + r[i];

                if(dp_tmp.containsKey(total_q) == false) {
                    dp_tmp.put(total_q, total_r);
                } else {
                    if(dp_tmp.get(total_q) > total_r) {
                        dp.put(total_q, total_r);
                    }
                }
                if(total_q >= M && min_cost > total_r) {
                    min_cost = total_r;
                }
                dp = dp_tmp;

            }
        }
        System.out.println(min_cost);
    }
}

Java: paiza事務局作成コード Vol.2 動的計画法

得点:100点
通過テストケース:7/7

import java.util.Scanner;
import java.util.List;
import java.util.ArrayList;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int m = scanner.nextInt();
        int n = scanner.nextInt();
        int[] q = new int[n];
        int[] r = new int[n];
        int sum_q = 0;
        int sum_r = 0;
        for (int i=0; i<n; i++) {
            q[i] = scanner.nextInt();
            r[i] = scanner.nextInt();
            sum_q += q[i];
            sum_r += r[i];
        }

        int dp_m = sum_q - m;
        int[] dp = new int[dp_m+1];

        for (int i=0; i<n; i++) {
            for (int j=dp_m; j >= q[i]; j--) {
                dp[j] = Math.max(dp[j], dp[j-q[i]] + r[i]);
            }
        }

        System.out.println(sum_r - dp[dp_m]);
    }
}

Java: paiza事務局作成コード Vol.1 O(2^n)

得点:71点
通過テストケース:5/7

import java.util.Scanner;
import java.util.List;
import java.util.ArrayList;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int m = scanner.nextInt();
        int n = scanner.nextInt();
        int[] q = new int[n];
        int[] r = new int[n];
        for (int i=0; i<n; i++) {
            q[i] = scanner.nextInt();
            r[i] = scanner.nextInt();
        }

        // m社のうちi番目の会社を使うか使わないかの表を作る
        // 3社とかなら
        //  A, B, C
        //  1, 1, 1
        //  1, 1, 0
        //  1, 0, 1
        // .....続く...
        // みたいな1を使う0は使わないの表を作る

        List<List<Integer>> use_list = new ArrayList<List<Integer>>();

        // 2進数で考えると
        for (int i=0; i<(1<<n); i++) {
            List<Integer> tmp = new ArrayList<Integer>();
            for (int j=0; j<n; j++) {
              tmp.add((i >> j) & 1);
            }
            use_list.add(tmp);
        }

        // 使う使わないリストから、人月を満たせる組み合わせで最安を探す
        int ans = 0;
        for (int i=0; i<n; i++) {
            ans += r[i];
        }
        for (int i=0; i<use_list.size(); i++) {
            int cost = 0;
            int ningetsu = 0;
            for (int j=0; j<use_list.get(i).size(); j++) {
                if (use_list.get(i).get(j) == 1) {
                    ningetsu += q[j];
                    cost += r[j];
                }
            }
            if (ningetsu >= m && ans > cost) {
                ans = cost;
            }
        }
        System.out.println(ans);
    }
}
ページの先頭へ戻る