【霧島京子】paiza Online Hackathon Lite をやってみました【動的計画法】

26歳 × (リボン+ミニスカ+ニーソ)というあざとさに負けたので、
paizaのオンラインハッカソンに挑戦してみました。

天才火消しエンジニア霧島「もしPMおじさんが丸投げを覚えたら」 | paizaオンラインハッカソン（POH）

問題見た瞬間、「あれ？またナップザック問題？」と思ったんですが、ナップザック問題でした。
第1回の野田ちゃんの時もナップザックだったような記憶があったので過去の自分の記事を読み返してみると、
「最初はナップザック問題かと思ったけど解説読んだらどうやら違ったようだ」
って感じだったようです。さすがに何回も同じ問題出さないよねー。

【アルゴリズム】新人女子の書いたコードを直すだけの簡単なお仕事をやってみた - 16bit!
【アルゴリズム】新人女子の書いたコードを直すだけの簡単なお仕事の解説を読んだ - 16bit!

まぁこの時に自分の脳内にナップザック問題（というか動的計画法）をインプットしたおかげで今回の問題が解けたので、
結果オーライです。

ソース晒し

package paiza.poh3;

import java.io.BufferedReader;
import java.io.InputStreamReader;


/**
 * Paiza Online Hackathon 3
 * 20万人月のプロジェクトを最も効率的に下請け会社に振る方法を算出する
 * @author sakuramochi
 *
 */
public class Main {
	
	public static void main(String[] args) throws Exception {
		//クラス生成
		Main self = new Main();
		self.executeMain();
    }
	
	private void executeMain() throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String line = br.readLine();
        final int m = Integer.parseInt(line); //1行目がプロジェクト総人月
        line = br.readLine();
        final int n = Integer.parseInt(line); //2行目が下請け会社の数
        
        int total_q = 0;
    	int total_r = 0;
    	int[] ary_q = new int[n];
    	int[] ary_r = new int[n];
        //下請け会社のリストを作成(たかだか50ループ)
        for (int i = 0; i < n; i++) {
        	String readLine = br.readLine();
            readLine = readLine.trim();
            String[] readLineArray = readLine.split(" ");
            int q = Integer.parseInt(readLineArray[0]);
            int r = Integer.parseInt(readLineArray[1]);
            total_q = total_q + q;
            total_r = total_r + r;
            ary_q[i] = q;
            ary_r[i] = r;
        }
        
        //削減できる人員
        int reduce_q = total_q - m;
        
        /*
         * sum(q) <= reduce_q を満たす中で、sum(r)が最大となる組み合わせを求めれば（⇒ナップサック問題）、
         * total_r - sum(r) が答え
         */
        
        //dp[i][j] : i番目までの会社を使う(=省く)場合の、人員j人以内での最大コスト
        int[][] dp = new int[n+1][reduce_q+1]; 
        for (int i = 0; i < n+1; i++) {
        	dp[i][0] = 0;
        }
        for (int j = 0; j < reduce_q+1; j++) {
        	dp[0][j] = 0;
        }
        
        //動的計画法
        for (int i = 1; i < n+1; i++) {
        	for (int j = 1; j < reduce_q+1; j++) {
        		if (ary_q[i - 1] <= j) {
        			dp[i][j] = Math.max(dp[i-1][j], dp[i-1][j-ary_q[i-1]] + ary_r[i-1]);
        		} else {
        			dp[i][j] = dp[i-1][j];
        		}
        	}
        }
        
        System.out.println(total_r - dp[n][reduce_q]);
	}
}

こんな感じ。
ポイントは「(全下請け会社の人員数) - m = 削減可能人数」を求めることで、
「削減可能な人員数以内に収まる中で、かかるコストが最大となる会社の組み合わせを求める」という、
「ナップザックの容量に収まる中で、価値が最大となる商品の組み合わせを求める」と同じ形式の問題にすり替えられるところ。
これさえできればあとは動的計画法のサンプルソースをコピペするだけで終わりです。

■結果
sakuramochiさんの採点結果[100点] 完璧ぃぃ！｜paizaオンラインハッカソンLite

とは言っても最速ではないと思うので、問題の特性を活かせばもうちょっと速くはできそうです。

終わり。