山傘のプログラミング勉強日記[Java & Unity]

プログラミングに関する日記とどうでもよい雑記からなるブログです。

AtCoder Beginner Contest 013 C - 節制

線形計画法

C - 節制

AtCoderの過去問を解いていて気になった問題です。この問題は線形計画問題に似ていると思います。

実行可能領域に端点がない?ので、境界に近い格子点を調べる必要があります。解説を見て解答作ったんですが、1つの変数を固定すれば残りの変数も自動的に決まるわな。

線形計画問題といえばシンプレックス法が有名ですが、もう覚えてないですね。シンプレックス法を使った問題とか出てきそうな予感がします。

コード

import java.util.Scanner;

public class ProblemC {
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        long N = scan.nextLong();
        long H = scan.nextLong();
        long A = scan.nextLong();
        long B = scan.nextLong();
        long C = scan.nextLong();
        long D = scan.nextLong();
        long E = scan.nextLong();
        scan.close();


        if(H - N * E > 0) {
            System.out.println(0);
            System.exit(0);
        }


        long ans = N * A;
        for(long i = 0; i <= N; i++) {
            long x = i;
            double y1 = (double)(N * E - H -(B + E) * x) / (D + E);
            long y;
            if(y1 < 0) {
                y = 0;
            }else {
                y = (N * E - H -(B + E) * x) / (D + E) + 1;
            }
            long t = A * x + C * y;
            if(ans > t) {
                ans = t;
            }
        }
        System.out.println(ans);
    }
}

参考サイト

下のサイトの解説が良くまとまっていました。 wk1080id.hatenablog.com