競プロ日記

問題
ACコード - 元コード(掲載コード)
ACコード - 初期化を分ける

#include <bits/stdc++.h>
#define GET_REP(_1, _2, _3, NAME, ...) NAME
#define rep(...) GET_REP(__VA_ARGS__, irep, _rep)(__VA_ARGS__)
#define rep1(...) GET_REP(__VA_ARGS__, irep1, _rep1)(__VA_ARGS__)
#define _rep(i, n) irep (i, 0, n)
#define _rep1(i, n) irep1(i, 1, n)
#define irep(i, a, n) for (int i = a; i < (int)(n); ++i)
#define irep1(i, a, n) for (int i = a; i <= (int)(n); ++i)
#define rrep(i, n) for (int i = (int)(n) - 1; i >= 0; --i)
#define rrep1(i, n) for (int i = (int)(n); i >= 1; --i)
#define allrep(X, x) for (auto &&X : x)
#define all(x) begin(x), end(x)
#ifdef LOCAL
  #include "../../Lib/cout_container.hpp"
  #define debug(x) cout << #x " => " << (x) << endl
#else
  #define debug(x) 0
#endif
using lint = long long;
constexpr int    INF  = 1 << 28;
constexpr lint   INFL = 1LL << 60;
constexpr int    MOD  = (int)1e9 + 7;
constexpr double EPS  = 1e-9;
using namespace std;
namespace { struct INIT { INIT() { cin.tie(0); ios::sync_with_stdio(false); cout << fixed << setprecision(15); } } INIT; }

int main(void) {
  int n, t;
  cin >> n >> t;
  vector<pair<int, int>> ab(n);
  rep (i, n) cin >> ab[i].first >> ab[i].second;
  vector<vector<int>> dpl(n + 1, vector<int>(t)), dpr(n + 1, vector<int>(t));
  rep1 (i, n) {
    int li = i - 1, ri = n - i;
    rep (j, t) {
      int lnext = j + ab[li].first, rnext = j + ab[ri].first;
      dpl[i][j] = max(dpl[i][j], dpl[i - 1][j]);
      if (lnext < t) dpl[i][lnext] = max(dpl[i][lnext], dpl[i - 1][j] + ab[li].second);
      dpr[n - i][j] = max(dpr[n - i][j], dpr[n - i + 1][j]);
      if (rnext < t) dpr[n - i][rnext] = max(dpr[n - i + 1][rnext], dpr[n - i + 1][j] + ab[ri].second);
    }
  }
  int maxi = 0;
  rep (i, n) {
    rep (j, t) {
      int sum = dpl[i][j] + dpr[i + 1][t - 1 - j];
      maxi = max(maxi, sum + ab[i].second);
    }
  }
  cout << maxi << endl;
  return 0;
}

件のひどいACを解き直した。
出題者さんの想定解法の「DPを2つに分けて足し合わせる」解法で実装した。
参加記事でも書いたがコンテスト中に思いついた方針は合っていて、「iを除いた最大値のDPをそれぞれ考えると良さそうだがO(N^2*T)になってしまうどうしよう」と悩んでいた。
2つに分けてDPがまさにこれを解決するための手段で頭に残りそうなのでこちらにした。

理解が及ばないということは全くなくて本来なら記事も書かないのだが、かなり基本的だが気をつけないといけない部分があったので忘れないようにメモしておく。

問題なのは37,39行目で、この部分を忘れていて少し時間がかかった。
例えば37行目は、1つ前のiの値dp[i-1][j]をdp[i][j]に持ってきているだけで、初期化に近い。
これをどのように書けばスマートかというのが気になるポイント。

38行目の状態の遷移には関係ないので、例えば初期化として遷移の前にまとめて以下のようにしても問題ないはずである。
rep(j, t) dp[i][j] = dp[i-1][j]

前の状態から値を持ってくる必要があるか考え、必要なら初期化として先にまとめて処理するのは忘れにくくて良さそうな気がするが、初期化も状態の遷移の1つであると考えると、遷移が無駄に分けられているのは気持ち悪いような感じもある。
初期化を分けた場合の違いとしては、ループを別に回すのでその分ほんの僅かに処理増加するかも？と、maxの比較が必要なくなるので前者よりは明らかに若干の高速化が期待できるが、これはあまり考えなくて良いだろう。
ちなみに今回の問題だと、初期化を分けることで112ms→103msと、少しだけ早くなった。

記事を書くために初期化を分けて書いてみたが、こちらの方がすっきり書けたように感じられた。
いつも参考にさせてもらっているkmjpさんのコードを見ると、元々のコードのように初期化として分けない実装になっている。
真似するのも良いが、割と好き好きな感じもあるので、今後は分ける方針で書いていきたい。
そろそろDPコンテスト(Education～の方)をやろうと思ってたので、最近色々経験したDPの手法とか方針とかを定着させていきたい。