日記

のみろぐ

主に競プロ日記です

DPL_1_C「ナップザック問題」

DPL_1_C「ナップザック問題

考察

  • DPに使いそうな値を考える
    • 今回は01ナップザックみたいに何個目まで選んだかという情報は必要無い
    • 価値と重さが分ればいいかなーってなる
  • 価値と重さだけわかれば良いので1次元のDPでできそう
  • 同じ種類の荷物は何個でも使うことができるため、コイン問題のように考えることができる。
  • なので、コイン問題みたいに解けばできそう
  • 考察終了!


解法

手順

f:id:nomikura:20180616055444p:plain:w300

  1. 上図のようなDPテーブルを作る
  2. DPテーブルを$0$で初期化する
  3. 漸化式を立てて、そのコードを書く

漸化式

$\begin{array}{ll} dp[i] = max(dp[i], dp[i-w[j]]+v[j]) & (j \geq w[j])\end{array}$


コード

#include <bits/stdc++.h>
using namespace std;

const int INF = 1e8;

int N, W;
int v[111], w[111];
int dp[11111];

int main() {
    cin >> N >> W;
    for (int i = 0; i < N; i++) { cin >> v[i] >> w[i]; }

    // DP
    for (int i = 0; i <= W; i++) {
        for (int j = 0; j < N; j++) {
            if (i >= w[j]) {
                dp[i] = max(dp[i], dp[i-w[j]]+v[j]);
            }
        }
    }

    cout << dp[W] << endl;

    return 0;
}


要点

  • DPに必要な情報が何かを考えること。
    • このとき考えるのは答えを求めるのに必要最低限の情報だけにする。
  • コイン問題に帰着できることに気がつくこと。

感想

  • 1次元のDPはだいたいコイン問題に帰着できる説が浮上しつつある(ホンマか?
  • なんとなくで解いたのでまだ確信が持てないという...

DPL_1_B「0-1 ナップザック問題」

DPL_1_B「0-1 ナップザック問題」

解法

f:id:nomikura:20180616043824p:plain:w450

  1. 上図のようなDPテーブルを用意する
  2. テーブルをすべて$0$で初期化する(グローバルに宣言していれば初期化する必要は無い)
  3. 漸化式を立て、それをコードとして書く


漸化式

$$ dp[i][j] = \left\{ \begin{array}{ll} max(dp[i-1][j], dp[i-1][j-w[i]]+v[i]) & (j \geq w[i]) \\ dp[i-1][j] & (j \lt w[i]) \end{array} \right. $$


部分的に見る

f:id:nomikura:20180616055904p:plain:w500

  • いきなり全体的なことを考えると頭が爆発するので一部分に注目してみる
  • $dp[i][j] = max(dp[i-1][j], dp[i-1][j-w[i]+v[i]])$という式について
    • maxの左側は$v[i]$を選ばない場合を表す
    • maxの右側は$v[i]$を選ぶ場合を表す
    • 両方の値を比較して大きい方が$dp[i][j]$になる


コード

#include <bits/stdc++.h>
using namespace std;

int N, W;
int v[111], w[111];
int dp[111][11111]; // dp[i][j]: 重さ制限jで個数iまで見たときの最大の価値

int main() {
    // 入力
    cin >> N >> W;
    // インデックスを1つずらしている
    for (int i = 0; i < N; i++) { cin >> v[i+1] >> w[i+1]; }

    // DP
    for (int i = 1; i <= N; i++) {
        for (int j = 0; j <= W; j++) {
            if (j >= w[i]) {
                dp[i][j] = max(dp[i-1][j], dp[i-1][j-w[i]] + v[i]);
            } else {
                dp[i][j] = dp[i-1][j];
            }
        }
    }
    cout << dp[N][W] << endl;

    return 0;
}
  • 便宜上、入力の際に重さと価値のインデックスを1つ先へずらした
  • 集めるDPはdp[i][j] = 遷移元の形にしたい。
  • 読みにくいかもだけど、書き方は他の問題も見て検討する


要点

  • $dp[i][j]$を求めるとき、$dp[i-1][W]$までは既に求められていることが前提となっている。
  • なので、$dp[i][j]$を求めたいときに、それ以前がどんな状態であるかは考える必要が無い。
    • これを頭に置いておかないと考えることが多くて頭が爆発する

ABC040-C「柱柱柱柱柱」

ABC040-C「柱柱柱柱柱

解法

  • 「$dp[i]$:$i$手目の最小コスト」というDPテーブルを作る
  • 後はDPする


コード

集めるDP

#include <bits/stdc++.h>
using namespace std;

using ll = long long;

const ll INF = 1e15;
int N;
ll a[111111];
ll dp[111111]; // dp[i]: i+1手目の最小コスト

int main() {
    cin >> N;
    for (int i = 0; i < N; i++) { cin >> a[i]; }

    // DPテーブル初期化
    fill(dp, dp+N+10, INF);
    dp[0] = 0;

    // DP
    for (int i = 0; i < N; i++) {
       for (int j = 1; j <= 2; j++) {
          if (i >= j) {
             dp[i] = min(dp[i], dp[i-j] + abs(a[i-j] - a[i]));
          }
       }
    }
    cout << dp[N-1] << endl;

    return 0;
}

配るDP

#include <bits/stdc++.h>
using namespace std;

using ll = long long;

const ll INF = 1e15;
int N;
ll a[111111];
ll dp[111111]; // dp[i]: i+1手目の最小コスト

int main() {
    cin >> N;
    for (int i = 0; i < N; i++) { cin >> a[i]; }

    // DPテーブル初期化
    fill(dp, dp+N+10, INF);
    dp[0] = 0;

    // DP
    for (int i = 0; i < N; i++) {
       for (int j = 1; j <= 2; j++) {
          if (i + j < N) {
             dp[i+j] = min(dp[i+j], dp[i] + abs(a[i] - a[i+j]));
          }
       }
    }
    cout << dp[N-1] << endl;

    return 0;
}


感想

  • 1次元のDPは大体同じ書き方なんだなーと思った
    • 外側にDPテーブルの最後まで走査するループを書く
    • 内側に遷移のパターンを列挙する
    • この辺のことは1次元のDPもうちょっと解いてからまとめるつもり
  • なので書くことがそんなにない
  • ただ、配る・集めるのどちらが良いか?みたいなところは悩ましいと思う

ABC099-C「Strange Bank」

ABC099-C「Strange Bank

考察

コンテスト中の考察

  • 価値の大きい金から使っていく貪欲で解けそう
  • 貪欲だと上手くいかない...
  • もしかしたらDPでは?→DP書けない

理想の考察

  • 本質部分はコイン問題と同じじゃん!!
  • 違う部分は使うコインの種類が与えられるのではなくて初めから決まっているという点。
  • $6^{a}, 9^{b}, 1$を使うから複雑そうに見えるけど、種類を全部列挙して「使うコインの種類」を表す配列に入れればシンプルになる。
  • すると、コイン問題と同じように解ける


コード

#include <bits/stdc++.h>
using namespace std;

const int INF = 1e8;
int N;
vector<int> c;
int dp[111111];

int main() {
    cin >> N;

    // コインの種類を配列に追加
    c.push_back(1);
    for (int i = 6; i <= N; i*=6) { c.push_back(i); }
    for (int i = 9; i <= N; i*=9) { c.push_back(i); }

    // DPテーブルを初期化
    fill(dp, dp+N+1, INF);
    dp[0] = 0;

    // DP
    for (int i = 0; i <= N; i++) {
        for (int j = 0; j < c.size(); j++) {
            if (i >= c[j]) {
                dp[i] = min(dp[i], dp[i-c[j]]+1);
            }
        }
    }

    cout << dp[N] << endl;

    return 0;
}


要点

  • コイン問題に帰着できることに気づくことが大事だった
  • いろんな種類のコインを1つの配列で管理してシンプルにする事が大事だった


感想

  • 典型力って大事だなーと思った。
  • コイン問題知ってるだけでこの問題解けたじゃん!!

DPログ

  • 解いたDPの解説記事を列挙していきます
  • 逐次更新
  • DP問題投げてくれると嬉しい

1次元DP


2次元DP


メモ

  • DPの本質はあるポイントに値を収束させることの繰り返しである(集めるDP)。
  • $dp[i]$を計算するとき、$dp[i-1]$までは計算済みであることが前提となっている。なので、$dp[i]$を求めるときはそれ以前がどういった状態であるかを考える必要は無い。このへんは結構シンプルな気がする。
  • DPで解こうとするときに大事なことは、最初にDPをするために必要な情報を考えてDPテーブルを作ることだと思う

DPの流れ

  1. DPテーブルを作る
    • 答えを求めるために必要最小限の情報を考える
    • 余計な情報はいらない
  2. DPテーブルを初期化する
  3. 漸化式を立てる
  4. コードを書く

DPL_1_A「コイン問題」

DPL_1_A「コイン問題

考察

  • 価値の高いコインから順番に使う貪欲法で解けるのでは?
  • でも、ちょうど$n$円払いたいので、貪欲ではうまくいかない時がある。
  • 例えば、$n=10, m=4, c = {1, 4, 6, 7}$のとき。大きいほうから払っていく貪欲だと$7+1+1+1$で合計$4$手になってしまう。
  • 5円になるまでの最小手数を求める→6円になるまでの最小手数を求める→7円...みたいなことができそう。これはDPで解けるのでは?


解法

f:id:nomikura:20180613150557p:plain

  1. 上記のような1次元のDPテーブルを用意する
  2. DPテーブルを初期化する
    • dp[0]は$0$、それ以外はINFで初期化する
  3. 漸化式をコードとして書く

漸化式

$$ dp[i] = min(dp[i], dp[i-c[j]+1]) \ \ (i \geq c[j]) $$

おまけ

  • $n=5, m=3, c={1,2,3}$のとき、DPは以下のように遷移する
  • 見ている要素に最適な値が収束する感じになる。
  • DPの本質は、あるポイントに値を収束させることの繰り返しなのでわかりやすいDPなんだと思う。

f:id:nomikura:20180613150617p:plain


コード

#include <bits/stdc++.h>
using namespace std;

const int INF = 1e8;
int n, m;
int c[22];
int dp[55555]; // dp[i]: i円になるまでのコインの最小枚数

int main() {
    // 入力
    cin >> n >> m;
    for (int i = 0; i < m; i++) { cin >> c[i]; }

    // DPテーブル初期化
    fill(dp, dp+n+1, INF);
    dp[0] = 0;

    // DP
    for (int i = 1; i <= n; i++) {
        for (int j = 0; j < m; j++) {
            if (i >= c[j]) {
                dp[i] = min(dp[i], dp[i-c[j]]+1);
            }
        }
    }
    cout << dp[n] << endl;

    return 0;
}


要点

  • DPの本質はあるポイントに値を収束させることの繰り返しであるということ。


類題


感想

  • 貪欲→DPを思いつける気がしない。
  • 上手いこと貪欲の反例が見つかれば良いけど、もっと複雑な問題だったら見つからない気がする...

ABC045-D「すぬけ君の塗り絵 」

ABC045-D「すぬけ君の塗り絵 / Snuke's Coloring

考察

  • 愚直に考えると、$HW$の盤面を用意してすべての座標に対し$9 \times 9$を全探索することになる。しかし、$HW$の最大値は$10^{18}$となるため全探索では間に合わない。
  • ここで入力の制約に注目すると、$N \leq 10^{5}$となっている。
  • 別に$HW$の座標全部見なくても関係のある部分だけ見ればいいんじゃね?ってところに気づく。
  • あと、なんか$9\times9が$白いマスのみの個数がたくさんありそう。黒マスを含む塊の個数はそれほど多くなさそう。
  • 答えを求めるのに関係のありそうな部分は、黒マスの周りの9この座標くらいだと気づく。
  • つまり、見るべき座標は最大でも$9N$個となる。見ている座標に黒マスが含まれているかどうかは$O(logN)$出判定できるので全体の計算量は$O(NlogN)$となる。

細かいこと

  • $9\times9$がすべて白いマスである個数の数え方を考える。
    • 初期値を$(H-2)(W-2)$とする。
    • $9\times9$に黒いマスがある場合、初期値から1を引く。これを繰り返すことで何も塗られていないマスの数がわかる。


解法

f:id:nomikura:20180607082258p:plain

  • 図のように、$9 \times 9$のマスにおいて黒マスが含まれるようなものを列挙したい。
  • なので、色つきのマスの周りの9つの座標をsetで持っておく。
  • 次に、そのマスから右下の$9\times9$にいくつ黒マスが含まれているかを数える。カウントした数はans[cnt]++のようにして答えに加算する。
  • 計算量は$O(NlogN)$となる。


コード

#include <bits/stdc++.h>
using namespace std;

using ll = long long;
using pii = pair<ll, ll>;

ll H, W, N;
ll A[111111], B[111111];
set<pii> coord, S; // 入力座標, 入力座標の周辺座標
ll ans[100];

// 黒マス周辺の9座標を列挙するための左上の座標をsetに格納する
void make(ll y, ll x) {
   for (int i = 0; i < 3; i++) {
      for (int j = 0; j < 3; j++) {
         int ny = y - i, nx = x - j;
         if (ny >= 1 && ny <= H-2 && nx >= 1 && nx <= W-2) {
            S.insert({ny, nx});
         }
      }
   }
}

int main() {
   cin >> H >> W >> N;
   for (int i = 0; i < N; i++) {
      cin >> A[i] >> B[i];
      coord.insert({A[i], B[i]});
      make(A[i], B[i]);
   }

   ll white = (H-2) * (W-2); // 9*9が白いマスの個数
   for (pii p : S) {
      ll y = p.first, x = p.second;
      int cnt = 0;
      for (ll i = y; i < y+3; i++) {
         for (ll j = x; j < x+3; j++) {
            if (coord.find({i, j}) != coord.end()) {
               cnt++;
            }
         }
      }
      if (cnt) white--;
      ans[cnt]++;
   }

   ans[0] = white;
   for (int i = 0; i <= 9; i++) {
      cout << ans[i] << endl;
   }


   return 0;
}

差分の列挙について

  • for分で$i, j(0 \leq i, j < 3)$について列挙する処理、上手いなあって感じ。
  • 僕は解いたとき$i, j(-2 \leq i, j \leq 0)$で回した。
  • でも、$0 \leq i, j < 3$で回してそれを座標から引くって言う処理の方が楽な気がする。


要点

  • 無駄な処理をしている部分を考えることが大事だった。
    • 今回の場合、白マスのみの部分を数えるのは無駄だった。
    • 無駄な部分を考えると計算量を落とすきっかけになることはよくある気がする。
  • 答えを求めるために関係のある部分のみについて考えることが大事だった。
    • すべての情報を見ていては間に合わないときにこの考え方を使うと良いのかなーと思う。
  • 無駄な処理を見つける→関係のありそうな部分を考えるっていう流れは大事かもしれない。


感想

  • 1度解いたことがあるので考察は一瞬だった。でも本番でこれを思いつける気はしない
  • 実装に時間がかかってしまった。結構複雑だよなー、これ。