AtCoder Beginner Contest 015_D_高橋くんの苦悩

DPの問題.ナップサック問題+α.スクリーンショットの重要度ってなんやねん.

atcoder.jp

問題の説明

枚数が $K$ 枚,幅が $W$ に収まる条件の下で画像を選ぶときの重要度の合計の最大値を求めよ.

条件

$1≦W≦10,000$
$1≦N≦50$
$1≦K≦N$

考えた事

枚数制限がない場合,これは典型的なナップサック問題と呼ばれるものとなる.

ja.wikipedia.org

(競プロでは)ナップサック問題はDPで解く事が一般的である*1.

garakutagoya.hatenablog.com

上の記事に記載の通り,DPの基本は変数の捜索にある.ナップサック問題でのDPによる使い方をかいつまんで話すと,荷物の添字を $i$ とし,重量の総和を $j$ とすると,「 $i$ 番目までの荷物で重量 $j$ 以下となるように荷物を選んだときの価値の最大値」として $dp_{i,j}$ テーブルを作ればよい.

今回であれば幅と重要度がそれに対応する.幅の制限を満たしながら重要度を最大とするように考えれば上のナップサック問題と何一つ変わらない.読者の皆様には簡単でしょう.

今回のポイントは枚数制限の要素が追加されている事だ.ナップサック問題でいうところの制限がもう1つ追加されている点に難しさがある.そこに注意してDPを考えてみよう.

ステップ1.全探索出来るかどうか

全探索する場合の計算量の見積もりをしよう.幅の制限は一先ず置いておき, $0~K$ 個選び,それ以外を選ばないくらいで考えると楽でいい.

$\sum_{k=0}^K {}_nC_k=2^K$

であるから計算量は $O(2^K)$ となりお察しの通り宇宙時間である.無念.

ステップ2.状態の遷移を考える

この問題の場合,前までの状態に写真を足せるかどうかで見ればよいだろう.その場合,幅,重要度はもちろんのこと写真の枚数が1枚増える事に注目するのが今回の大きなポイントである.オタクの部屋と違って普通の人は部屋に物を増やしたがらない.

ステップ3.変数を見つけ,配列の表を書く

遷移する変数を考えてみよう.この場合鍵となるのは小さい範囲で状況の変化を考えてみる事だ.もしスクリーンショットを選んだとしよう,その場合に変化するものは枚数,幅の合計,重要度の合計,そして画像を選んだという事実である.枚数,幅,選択した画像が分かっていれば重要度の合計を求める事が出来る.したがって上の3つを変数として考えてみよう.

イメージとしては $f(枚数,幅の合計,使用可能な画像の種類)=(重要度の合計)$ と思ってもらえれば差し支えない.

枚数を $0≦k≦K$ ,使用可能な画像の添字を $0≦i≦N$ ,幅の合計を $0≦j≦W$ として表を書いてみる.この場合,表を一度に書くと3次元を記述する事になってしまうため, $k$ の値で分けて書くとよい*2.

f:id:hikki-dominion:20220416134833j:plain

入力例1を用いて作成した表を以上に載せた.遷移している部分を赤と青で記しているが,3次元であるためどこが遷移しているのかまだ難しいだろう.私自身もこれだけでは $60$ がどこから来たものか分からず考えてしまった.

次のステップで遷移について考えてみよう.

ステップ4.漸化式の作成

ここからは漸化式の作成に入る.キーとなるのは状態の変化の仕方が画像を選んだ/選んでいないで二分される事だ.

まずは $i$ 枚目の画像を選べない場合を仮定しよう.この場合, $j\lt A_i$ が条件となる.選べない場合,枚数も,幅の合計も一切変わらない.変わる部分といえば $i$ 枚目を使わないという事は $i-1$ で考えても変わらない, $i$ を $i-1$ にしてもよい点だろう.

つまり,

$k→k$
$i→i-1$
$j→j$

としてよいのである.したがって,

$dp_{k,i,j}=dp_{k,i-1,j}(j\lt A_i)$

となる.

次に $i$ 枚目の画像を選べる場合を考える.もし選ばないならば $k,i,j$ の遷移は選べない場合と全く変わらない.

選ぶ場合,使用可能な枚数は $1$ 枚減り,幅も $A_i$ 減る. $i$ 番目を使う事が分かっていれば,足し算の線形性と同じ画像は2度使わない制約から,後は $i-1$ の場合で考えてよい.そして重要度は $B_i$ 上がる.そしてDPには選ぶ選ばないいずれかの重要度の合計の最大値を記載する事を繰り返せばいい*3.

そのため,

$k→k-1$
$i→i-1$
$j→j-A_i$

$dp_{k,i,j}=max(dp_{k,i-1,j}, dp_{k-1,i-1,j-A_i}+B_i)(j≧A_i)$

となる.まとめると,

$dp_{k,i,j}=dp_{k,i-1,j}(j\lt A_i)$

$dp_{k,i,j}=max(dp_{k,i-1,j}, dp_{k-1,i-1,j-A_i}+B_i)(j≧A_i)$

となる.初期条件としては

$dp_{k,i,j}=0(k=0∨i=0∨j=0)$

とすると分かりやすいだろう.

ステップ5.漸化式を元に配列を埋める

実装をするにあたってどうしたらいいだろう.ここまで読んでいただけた方ならお分かりの通り,3次元配列を用いる.

vvvll dp(K + 1, vvll(N + 1, vll(W + 1, 0)));

としてDP配列を作る.初期条件は $dp_{k,i,j}=0(k=0∨i=0∨j=0)$ だけで十分であるが,(何もない)= $0$ としても齟齬は生じないためそうしている.距離コストの最小値を求める場合,この部分が $INF$ になる事もあるため注意が必要だ.

後は3重ループを回し,配列を埋めればよい.

if (j < ab.at(i - 1).at(0)) {
                    dp.at(k).at(i).at(j) = dp.at(k).at(i - 1).at(j);
                } else {
                    dp.at(k).at(i).at(j) =
                        max(dp.at(k).at(i - 1).at(j),
                            dp.at(k - 1).at(i - 1).at(j - ab.at(i - 1).at(0)) +
                                ab.at(i - 1).at(1));

漸化式の部分はこのようになる.計算量は $O(K×N×W)$ となり,高々 $O(10^7)$ となるため,やや危ないが間に合う.

ステップ6.求めたい配列の値を見て答えを導く

$dp_{K,N,W}$ を見て,それを出力すればいい.なかなかタフな問題であった.

プログラム

#include <bits/stdc++.h>
using namespace std;
#include <atcoder/all>
using namespace atcoder;
using ll = long long;
using ld = long double;
using P = pair<int, int>;
using Graph = vector<vector<int>>;
using vi = vector<int>;
using vl = vector<long>;
using vll = vector<long long>;
using vvi = vector<vi>;
using vvl = vector<vl>;
using vvll = vector<vll>;
using vvvll = vector<vvll>;
using vs = vector<string>;
using pii = pair<long long, long long>;
using mint = modint1000000007;
const long double EPS = 1e-10;
const long long INF = 1e18;
const long double PI = acos(-1.0L);
#define reps(i, a, n) for (ll i = (a); i < (ll)(n); i++)
#define rep(i, n) for (ll i = (0); i < (ll)(n); i++)
#define rrep(i, n) for (ll i = (1); i < (ll)(n + 1); i++)
#define repd(i, n) for (ll i = n - 1; i >= 0; i--)
#define rrepd(i, n) for (ll i = n; i >= 1; i--)
#define ALL(n) begin(n), end(n)
#define IN(a, x, b) (a <= x && x < b)
#define INIT                          \
    std::ios::sync_with_stdio(false); \
    std::cin.tie(0);
template <class T>
inline T CHMAX(T& a, const T b) {
    return a = (a < b) ? b : a;
}
template <class T>
inline T CHMIN(T& a, const T b) {
    return a = (a > b) ? b : a;
}

int main() {
    ll W;
    cin >> W;
    ll N, K;
    cin >> N >> K;
    vvll ab(N, vll(2));
    rep(i, N) {
        rep(j, 2) { cin >> ab.at(i).at(j); }
    }
    vvvll dp(K + 1, vvll(N + 1, vll(W + 1, 0)));
    rrep(k, K) {
        rrep(i, N) {
            rrep(j, W) {
                if (j < ab.at(i - 1).at(0)) {
                    dp.at(k).at(i).at(j) = dp.at(k).at(i - 1).at(j);
                } else {
                    dp.at(k).at(i).at(j) =
                        max(dp.at(k).at(i - 1).at(j),
                            dp.at(k - 1).at(i - 1).at(j - ab.at(i - 1).at(0)) +
                                ab.at(i - 1).at(1));
                }
            }
        }
    }
    cout << dp.at(K).at(N).at(W) << endl;
}