AtCoder Beginner Contest 015

[競技プログラミング,競プロ解説]

AtCoder Beginer Contest 015 - D

• AtCoder Beginer Contest 015 - D 高橋くんの苦悩

  解説

• AtCoder Beginner Contest 015 解説

  解説の解説

• 問題自体は動的計画法 - ナップサック問題の01ナップサック問題と同じ
  • なので、ナップサック問題をやったことがなければそちらを先に理解したほうがよさげ

• しかし、制約条件に表計算ソフトに貼り付け可能なスクリーンショットの枚数Kが定義されているのでそれを考慮する
  • 品物の重さW　≒　スクリーンショットの幅A
  • 品物の価値V　≒　スクリーンショットの重要度B
  • なし　　　　≒　　スクリーンショットの枚数制限K

• 配列の構成
  • 01ナップサック問題：二次元配列 C[N+1][W+1] ← C[品物の数+1][容量+1]
  • 本問題：　　　　　　三次元配列 C[N+1][K+1][W+1] ← C[スクショの数+1][枚数制限+1][幅+1]
    • データの持ち方は結構重要で、このやり方でないと無限にバグる
    • いかにこのデータの持ち方をすぐに思いつき、なおかつ漸化式を閃くかが勝負のポイントか

• 解説に合わせてdpテーブルを定義してみる

dp[i][j][k]の定義

i 番目以下のスクショから j 個以下選び、幅 k がW を超えないようにスクショを選んだ時の価値の最大値

• 3次元DPのポイントとしては、dp[i][j][k]があった場合、iに対して複数表があるとイメージすればよい

• 漸化式
  • やっぱり表を作って地道に漸化式を立てるしかないように思う
  • dp[i][j][k] = \begin{eqnarray} \left\{ \begin{array}{l} max(dp[i-1][j][k], dp[i-1][j-1][k-A_i] + B_i) \\ max(dp[i-1][j][k], dp[i][j][k-1]) \end{array} \right. \end{eqnarray}

• 試作コード（Ruby）
  • 残念ながらRubyでは100msほど間に合わない（工夫して2次元DPにすれば通る）

lines = $stdin.read
array = lines.split("\n")
W = array[0].to_i
N,K = array[1].split(" ").map(&:to_i)
A = [0].concat(array[2..2+N].map{|s| s.split(" ").first.to_i})
B = [0].concat(array[2..2+N].map{|s| s.split(" ").last.to_i})

dp = Array.new(N+1).map{Array.new(K+1).map{Array.new(W+1, 0)}}

for i in 1...N+1
  for j in 1...K+1
    for k in 1...W+1
      if k >= A[i]
        dp[i][j][k] = [
          dp[i-1][j][k],
          dp[i-1][j-1][k-A[i]] + B[i]
        ].max
      else
        dp[i][j][k] = [
          dp[i-1][j][k],
          dp[i][j][k-1]
        ].max
      end
    end
  end
end

#dp.each_with_index do |l,i|
#  puts "i=#{i}"
#  dp[i].each{|ll| p ll}
#end

puts dp[N][K][W]

• コード（D言語）
  • D言語なら変なマクロ使わなくてもスマートに書ける

import std.stdio;
import std.conv;
import std.string;
import std.format;
import std.algorithm;
 
//string lines = q"[
//abcdeffg]";

void main()
{

  string lines;
  string buf;

  while (!stdin.eof) {
    buf = stdin.readln();
    lines ~= buf;
  }

  string[] array = splitLines(lines);
  
  int W = array[0].to!int;
  int N,K;
  N = array[1].split(" ")[0].to!int;
  K = array[1].split(" ")[1].to!int;
  
  int[] A = [0];
  int[] B = [0];
  for (int i=2; i<array.length; i++) {
    string s = array[i];
    A ~= s.split(" ")[0].to!int;
    B ~= s.split(" ")[1].to!int;
  }

  int[][][] dp = new int[][][](N+1, K+1, W+1);
  for (int i=1; i<N+1; i++) {
    for (int j=1; j<K+1; j++) {
      for (int k=1; k<W+1; k++) {
        if (k >= A[i]) {
          dp[i][j][k] = max(
            dp[i-1][j][k],
            dp[i-1][j-1][k-A[i]] + B[i]
          );
        } else {
          dp[i][j][k] = max(
            dp[i-1][j][k],
            dp[i][j][k-1]
          );
        }
      }
    }
  }

  writeln(dp[N][K][W]);
}