「経費精算で損しないために」の続き

GMOペパボ Advent Calendar 2019の記事ではありません。(面白い記事がたくさんあるのでぜひチェックしてみてください!!1)

この記事は何?

弊社アドベントカレンダーの5日目に同僚のakht氏がこのような記事を書きました。

akhtikd.com

akht氏は競技プログラミング(以下、競プロ)にハマっており、それを活かして身近にある問題を競プロっぽく見立てて解決したという面白い記事です。ぜひお読みください!(この記事より先に読んで)

で、今日そんなakht氏が社Slackの某チャンネルでこのような発言をしていました。

f:id:purple_jwl:20191205223445p:plain

(ちなみに文章中のモザイクは社Slackで僕を表すときによく使用される絵文字です)

なんか突然捧げられてしまった...

ということでこれを解いていきます、という謎な記事です。

解法

問題文は上記の記事をご覧ください。

akht氏のリクエストでは1 ≦ N ≦ 100でも解けるようにしてくれとのことでした。おそらく解けているであろうコードを先に貼っておきます。(即席でざっと書いたやつなのでバグってたらすまん!)

#include <bits/stdc++.h>

using namespace std;

int main() {
  // 領収書の枚数 : n
  // 経費精算できる金額 : m
  int n, m;
  cin >> n >> m;

  // 領収書の金額 : r
  vector<int> r(n);
  for (int i = 0; i < n; i++) cin >> r[i];

  vector<bool> dp(m + 1, 0);
  dp[0] = 1;
  vector<int> prev(m + 1, -1);
  int ans = 0;

  // 最適解を求める
  for (int i = 0; i < n; i++) {
    for (int j = m; j >= 0; j--) {
      if (!dp[j]) continue;
      int next = j + r[i];
      if (next > m || dp[next]) continue;
      dp[next] = 1;
      prev[next] = j;
      ans = max(ans, next);
    }
  }

  // 使った領収書を求める(復元)
  int tmp = ans;
  vector<bool> used(n, 0);
  for (int i = n - 1; i >= 0; i--) {
    if (tmp - r[i] >= 0 && prev[tmp] == tmp - r[i]) {
      used[i] = 1;
      tmp -= r[i];
    }
  }

  // 結果を出力
  for (int i = 0; i < n; i++) {
    cout << (used[i] ? r[i] : 0) << ' ';
  }
  cout << endl;
  cout << "Total: " << ans << endl;
}

O(2^N)ではとても厳しいので動的計画法(以下、DP)を用いて解きます。

「DPとは?」みたいな記事はインターネット上にたくさんあるので、気になる方は調べてみてください。

やっていることは大きく分けて2つで、DPで最適解を求めること復元です。

DPについてはあまり言うことがないのですが、配列に領収書の金額を組み合わせてこの金額にできるかどうかを持たせてやれば良いです。

そして今回重要なのが復元です。どの領収書を選ぶかが重要なので、最適解を求めたときにどれを選んだのか分かるようにします。コードのようにdpを更新するときにどの値から更新されたのかをprevに保存しておきます。これによって逆にたどっていけば復元することができます。

経費精算できる金額をMとすれば、O(NM)くらいで解くことができます。これなら十分高速に解を求められるし、毎月経費精算ができますね。めでたしめでたし。

さいごに

身近な問題を競プロっぽく解くのは面白いですね。競プロはネトゲみたいなところもありますが、実際にはこのような身近な問題を解決することができたりするので、少しでも気になった方はぜひ競プロに挑戦してみてください!

さいごのさいごに

ちなみに今回のakht氏のリクエストからすると、1ヶ月分のランチの領収書が100枚になる可能性があるということで「なんかやべえな??」って感じがします。