日記

のみろぐ

主に競プロ日記です

ICPC2018国内予選参加記

ICPCに挑むまで

  • 4月くらいに競プロ部に入って仲間を見つけた。わーい

メンバー

  • IDがわかんないから紹介できないという。全然交流しなかったね。
  • 色は水灰灰でっつ

コンテスト中

A問題

  • 後輩君が通しました

C問題

  • 僕が担当したやつ
  • 累積和と2分探索でいけるんじゃね?おいおい天才かよ...とか思ったけどなんかバグりました

B問題

  • 後輩君にまかせたけど無理って言われたから考えた
  • 実装考えてたら残り時間20分くらいになったので諦めました

2コマ漫画

感想

  • 思ったより自分が弱くてビビった(正直3完はできるとか思ってた)
  • 悔しい
  • 過去問全然解いてないという(は?)。埋めましょう
  • 来年は4完早解きしたいね

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を思いつける気がしない。
  • 上手いこと貪欲の反例が見つかれば良いけど、もっと複雑な問題だったら見つからない気がする...