TakahiroNakamori

TakahiroNakamori

中森崇博(ナカモリタカヒロ)

09 /
19
2021
 

【ABC219-Dの反省】 300の3乗は大丈夫だった

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

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

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

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

D問題について

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

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

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

  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のジャッジでは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についてはまだなんとなく実装している感じが強い。したがって、言語化が不十分だなと思います。引き続き、書いていくことでなんとかわかりやすくメモできるようにしたい。