競プロ日記

問題
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) (x).begin(), (x).end()
#ifdef LOCAL
  #include "../../Lib/cout_container.hpp"
  #define debug(x) cerr << #x " => " << x << endl
#else
  #define debug(x) 0
#endif
using lint = long long;
constexpr int    INF  = 1 << 30;
constexpr lint   INFL = 1LL << 62;
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; }

template 
class ModInt {
  long long n_;

  public:
  constexpr ModInt(const long long num = 0) : n_(num % mod_num) {}
  constexpr const long long&value() const { return n_; }
  constexpr bool   operator==(const ModInt &r) const { return this->n_ == r.n_; }
  constexpr bool   operator==(const long long &r) const { return this->n_ == r; }
  constexpr bool   operator!=(const ModInt &r) const { return this->n_ != r.n_; }
  constexpr bool   operator!=(const long long &r) const { return this->n_ != r; }
  constexpr bool   operator<(const ModInt &r) const { return this->n_ < r.n_; }
  constexpr bool   operator<(const long long &r) const { return this->n_ < r; }
  constexpr bool   operator>(const ModInt &r) const { return this->n_ > r.n_; }
  constexpr bool   operator>(const long long &r) const { return this->n_ > r; }
  constexpr bool   operator<=(const ModInt &r) const { return this->n_ <= r.n_; }
  constexpr bool   operator<=(const long long &r) const { return this->n_ <= r; }
  constexpr bool   operator>=(const ModInt &r) const { return this->n_ >= r.n_; }
  constexpr bool   operator>=(const long long &r) const { return this->n_ >= r; }
  constexpr ModInt operator+(const ModInt &r) const { return ModInt(*this) += r; }
  constexpr ModInt operator-(const ModInt &r) const { return ModInt(*this) -= r; }
  constexpr ModInt operator*(const ModInt &r) const { return ModInt(*this) *= r; }
  constexpr ModInt operator/(const ModInt &r) const { return ModInt(*this) /= r; }
  constexpr ModInt operator+(const long long &r) const { return ModInt(*this) += ModInt(r); }
  constexpr ModInt operator-(const long long &r) const { return ModInt(*this) -= ModInt(r); }
  constexpr ModInt operator*(const long long &r) const { return ModInt(*this) *= ModInt(r); }
  constexpr ModInt operator/(const long long &r) const { return ModInt(*this) /= ModInt(r); }
  friend ModInt operator+(const long long &l, const ModInt &r) { return ModInt(l) += r; }
  friend ModInt operator-(const long long &l, const ModInt &r) { return ModInt(l) -= r; }
  friend ModInt operator*(const long long &l, const ModInt &r) { return ModInt(l) *= r; }
  friend ModInt operator/(const long long &l, const ModInt &r) { return ModInt(l) /= r; }
  constexpr ModInt &operator++() { return *this += 1; }
  constexpr ModInt &operator--() { return *this -= 1; }
  constexpr ModInt &operator+=(const ModInt &r) {
    n_ += r.n_;
    if (n_ >= mod_num) n_ -= mod_num;
    return *this;
  }
  constexpr ModInt &operator-=(const ModInt &r) {
    if (n_ < r.n_) n_ += mod_num;
    n_ -= r.n_;
    return *this;
  }
  constexpr ModInt &operator*=(const ModInt &r) {
    n_ = n_ * r.n_ % mod_num;
    return *this;
  }
  constexpr ModInt &operator/=(ModInt r) {
    long long exp = mod_num - 2;
    while (exp) {
      if (exp & 2) *this *= r;
      r   *= r;
      exp /= 2;
    }
    return *this;
  }
  friend istream &operator>>(istream &is, ModInt<mod_num> &r) {
    is >> r.n_;
    r.n_ %= r.mod_num;
    return is;
  }
  friend ostream &operator<<(ostream &os, const ModInt<mod_num> &r) { return os << r.n_; }
  explicit operator int() const { return n_; }
  explicit operator long long() const { return n_; }
  explicit operator double() const { return n_; }
};

using mint = ModInt;
vector<vector<vector>> dp;
int main(void) {
  int n, k;
  cin >> n >> k;
  dp.assign(n + 1, vector<vector>(n + 1, vector(k + 100)));
  dp[0][0][0] = 1;
  rep (i, n) {
    rep (j, i + 1) {
      rep (l, k + 1) {
        dp[i + 1][j][l + 2 * j] += dp[i][j][l];
        dp[i + 1][j + 1][l + 2 * (j + 1)] += dp[i][j][l];
        dp[i + 1][j][l + 2 * j] += dp[i][j][l] * j * 2;
        if (j > 0) dp[i + 1][j - 1][l + 2 * (j - 1)] += dp[i][j][l] * j * j;
      }
    }
  }
  cout << dp[n][0][k] << endl;
  return 0;
}

むーずかしくなーーーーーい？？？？？
箱根駅伝DPってなんやねん。
箱根駅伝DPを知っていることの難しさに加え、kの遷移について工夫する必要がある点についても考えると、これマジでABCか？って感じ。
個人的今まで解いたABC最難問(最理不尽)は今でもサプリメントだが、典型の難しさと工夫の難しさは過去最高じゃないかなぁという気がする。

それと今回配るDPを使った。
貰うDPと配るDPの違いはあまり詳しく見ていなかったものの、書いていたらこういうことなんだろうなというのがここ1ヶ月くらいで分かってきた。
貰うDPの方が好きなのだが、さすがに今回は配るDPの方が書きやすそう。
ここで配るDP初心者の罠。
kの遷移ではkより大きい値は持ち得るのは分かるものの、kより大きいdpの値は答えとなるdp[n][0][k]には影響を及ぼさない(よね？)し、配るDPなら配列外参照しても答えには関係ないし、ということで気軽に配列外参照してやったのだが、全然ダメだった。
そういやC++って配列外参照したら既にあるデータ破壊することがあったわ・・・。
さすがに昔からC++使ってるのでWAの後すぐに気付けたが、本番ならWAカウント1だもんなぁ。
いつか読んだDPの配列は最大値プラスいくつか余裕持っておこうねが頭によぎる。
件のサプリメントでDPは最初に要素数決定しておいた方が良いかも、と少し考えたものの、自分がコンテストで競うよりも勉強に重点を置いていることを考えると、要素数を最大値と置くよりも入力値から最大値を決定した方がDPの状態・遷移を追えると思ったのでそのようにしていた。
入力値を使うにしても余裕をどれくらい持たせるべきかを把握して、いついかなるときも配列外参照はダメ！と思っておこう(C++の基本)。
以下本題。


最初問題読み間違えて順列部分を見落としていた。
「絶対値だから0の場合は1通り他の場合は±で2通りあるから分けてDP遷移させよう」なんて考えたけど全然違った。
全く思いつかなくてPDF解説読んだけど解説もむずかC。
読み間違えてていたとは言え、DPで解けそうという部分があってたのはgoodポイント。
YouTubeの解説の説明部分を軽く見て理屈を理解した気持ちになり、実際に実装してみるも答えが合わない。
見比べてみるとkの遷移が間違っていた。
動画やその他ブログ等で正しい遷移を調べてみるも、なぜそんな遷移になるのか全く分からなかった。
理解にかなり手間取ったので考え方をメモしておく。


今までやってきて知っているDPには、「その状態で確定した値」を入れていた。
この表現もそのまま聞いてもなんのことやらだが、簡単に言うとその状態で実際に数え上げたらその値になるということだ。
今回の問題で同じようなDPを考えるとうまく行かない。
Kの遷移のうち、保留していた点と新しい点をつなげる場合、増加する奇妙さkはどの点を保留しているかによって変わってしまう。
そうすると、どの点を保留しているかについても情報を保持する必要がある上、kの遷移も保留している点それぞれに行う必要が出てきてしまう。

今回のDPはそうではなくて、「その状態で最低限持ち得ることが保証された値(その状態が持つポテンシャル)」を入れる。
DPの遷移はYouTubeの解説通り(新しい点同士を繋ぐ), (新しい点をどちらも繋がない), (新しい点の片方と保留した点を繋ぐ), (新しい点の両方と保留した点を繋ぐ)の4つがある。
どの遷移についても保留した点を繋ぐのは新しい点であることから、保留した点は保留した点同士繋ぐことはないことが分かる。

次に、今見ているi段目の新しい点について、保留した点と繋がない遷移をする場合を考える。
その次のi+1段目の新しい点と保留した点を繋ぐことを考えると、i段目で繋ぐよりも1つ多く交差することになる。
また最終的には、保留した点は全て繋がれる必要があることから、今まで保留した点j個全ての点が1つ多く交差すると考えて良い。
よって、kを遷移させるときは、保留した点が左右で2つあることも踏まえて、(次のi+1段目で保留する点の個数)×2を足し合わせる。
なお、DPの遷移上、「残り1段しかないのに保留している点が10個ある」なんてことにもなるが、このような値は答えに影響しない。

このように考えると、新しい点と保留した点を繋ぐ遷移は、今まで足してきた「最低限持ち得ることが保証された値」を実際の値に確定させる遷移であるとも言える。
すると、新しい点と保留した点を繋ぐ遷移よりも、繋がない遷移の方がkの増加量が多いのは、「値を確定させる=i+1段目の遷移で交差できる点が減る」と捉えられるため直感的にも理解できる。
少なくとも自分はこのように理解している。


この実際の値としてはおかしい「最低限持ち得ることが保証された値」を保持するのは、「点を保留する」という、実際の状態としてはおかしい状態を保持するからだと考えている。
例えば、ナップサック問題についてのDPを考える場合、[特定の重さまで][特定の番目の品物まで]を状態として持つ。
これらの遷移は全て問題の条件としてありえる値である。
しかし今回のDPでは、[点を特定の個数保留する]という状態を持つが、点を保留した状態なんていうのは問題で許されていない。
最終的には必ず全ての点同士が繋がれていなければならない。
この中間値専用の仮想の状態が、特殊なkの遷移を生み出す。
先程も書いたような、どの点を保留しているかまで保持するようなDPを(時間やメモリの問題は置いておいて)考えると、このような特殊な遷移ではなく、毎回kの増加量を計算して足し合わせる一般的な遷移ができるのだが、この特殊な遷移が時間やメモリを節約するために工夫した部分となるのだろう。