2021年9月18日に開催された サイシードプログラミングコンテスト2021（AtCoder Beginner Contest 219）（以下、ABC219） に参加しました。

サイシードプログラミングコンテスト2021（AtCoder Beginner Contest 219） – AtCoder

プログラミング初級者から上級者まで楽しめる、競技プログラミングコンテストサイト「AtCoder」。オンラインで毎週開催プログラミングコンテストを開催しています。競技…

atcoder.jp

結果は以下の通りでした。

• 3完（A,B,C） 0WA
• 順位: 2451位
• パフォーマンス: 917
• レーティング: 707 → 730

ここではD問題について復習します。

D問題について

問題等は以下のリンクをご確認ください。

D – Strange Lunchbox

プログラミング初級者から上級者まで楽しめる、競技プログラミングコンテストサイト「AtCoder」。オンラインで毎週開催プログラミングコンテストを開催しています。競技…

atcoder.jp

コンテスト中に思いついたことは以下の通りです。

1. X,Yの値によって、弁当の選ぶ、選ばないのパターンが変わるから、たこ焼きやたい焼きの数で並べ替えるとかじゃぁ対応できない。
2. ナップサックっぽい方法（DP）で対応できないかなぁ？

DPでなんとかできないかと考えたのですが、\(N,X,Y \leq 300\)だから、\(O(NXY)\)でループが \(300^{3} = 27,000,000\) 回になってTLEになるからダメだな、と思い別の方法を考えていたのですが、特に何も思い付かず時間切れとなりました。

AtCoderのジャッジでは1秒あたり\(10^8\)回程度の計算が可能

AtCoderの「C++入門 AtCoder Programming Guide for beginners (APG4b)」の「EX21 – 計算量の見積もり」に計算量についての目安が書いてありました。

EX21 – 計算量の見積もり

プログラミング初級者から上級者まで楽しめる、競技プログラミングコンテストサイト「AtCoder」。オンラインで毎週開催プログラミングコンテストを開催しています。競技…

atcoder.jp

AtCoderのジャッジでは1秒あたり\(10^{8}\)回程度の計算が可能です。

\(10^8 = 100,000,000\)なので、\(300^{3}\)だったら最後まで考えてよかったということになります。

DP(動的計画法)について

ということで、コンテスト終了後になってしまいましたが、ACしたコードは以下になります。

#include <bits/stdc++.h>
using namespace std;
#include <atcoder/all>
using namespace atcoder;
using ll = long long;
using P = pair<int, int>;
#define rep(i, n) for(int i = 0; i < (n); ++i)
// const int mod = 1000000007;
// const ll INF = 1LL<<60;
const int INF = 1001001001;

int main() {
  int N, X, Y;
  cin >> N >> X >> Y;

  vector<int> A(N), B(N);
  rep(i, N) { cin >> A[i] >> B[i]; }

  vector<vector<int>> dp(X + 1, vector<int>(Y + 1, INF));

  dp[0][0] = 0;

  for(int i = 0; i < N; ++i) {
    for(int j = X; 0 <= j; --j) {
      for(int k = Y; 0 <= k; --k) {
        int a = max(0, j - A[i]);
        int b = max(0, k - B[i]);
        dp[j][k] = min(dp[j][k], dp[a][b] + 1);
      }
    }
  }

  if(dp[X][Y] == INF) {
    cout << "-1" << endl;
  } else {
    cout << dp[X][Y] << endl;
  }
  return 0;
}

ポイントをメモしておきます。

• dp[j][k]:= j 個のたこ焼き、k 個のたい焼きを得ることができる弁当の最小値（初期値はINF）。
• 後ろから考えた方が楽そう。
• i 番目の弁当を選択したとき、たこ焼きは A[i] 個得ることができる。 X 個得るのに必要な数（j – A[i] = a）を全パターンループで回す。
• a や b は 0 以上じゃないとダメ。
• dp[a][b] + 1 の + 1 が選択した i 番目の弁当のこと。dp[a][b]は残りを達成するための最低の弁当の数。

DPについてはまだなんとなく実装している感じが強い。したがって、言語化が不十分だなと思います。引き続き、書いていくことでなんとかわかりやすくメモできるようにしたい。