yukicoder No.93 ペガサス
問題名, 「ひま」でも良かったと思います。
解法
writer の解説がわかりやすいのであんまり言うことがないです。
ペガサス - 解説
ただ dp の遷移が結構難しいというか面倒です。
ソースコードでコメントの説明をつけましたが少しだけ補足します。
解説ページで説明しているように dp を作っていますが, for 文で回すのは n と 条件を満たさない隣接関係の総数 のみにして, 他のフラグはすべて for 文の中で場合分けしています。
others とコメントがついてるところは, ng な並び方をしていないペアの間に n+1 を入れる場合(例えば {1,5})ですが, これは ng なペアの数及び n-1 の隣以外の場所なので, 大抵の場合は (n+1 個) - (ng+2 個) だけあります。たまに 引く数が (ng+1) 個の場合がありますがこれは n-1 の隣になるものが n-1 と n-3 で ng 回避するものと 単純に n-1 のとなりにするもので分かれているからです。
得た知見
- 難しい動的計画法では, 「n 個目の要素をどのように今の状態に組み込んでいくか」が大事
- 今回は n*n の並びから (n+1)*(n+1) の並びを作るために n+1 個目の要素は n 個の要素の間のどこかに入れていく感じだった
- 状態をなるべく簡素に保つ
- 難しい dp の要はここですね。これだけ言っても何もって感じですが
const int MAXN = 1003; const ll MOD = 1e9+7; ll dp[MAXN][MAXN][2][2]; // n, ng, (n-3,n-1), (n-2, n) -> num inline void add(ll& a, ll b) { (a += b) %= MOD; } int main() { cin.tie(0); ios::sync_with_stdio(false); int N; cin >> N; if (N <= 2) { cout << N << endl; return 0; } dp[2][0][0][0] = 2; for (int n = 1; n < N; n++) for (int ng = 0; ng < n; ng++) { // (n-3, n-1) (n-2, n) ll v = dp[n][ng][1][1]; if (v) { // split n-2, n add(dp[n+1][ng-1][0][0], v); // split n-3, n-1 add(dp[n+1][ng][1][1], v); // adjacent to n-1 add(dp[n+1][ng+1][1][1], v); // split others add(dp[n+1][ng-1][1][0], v*(ng-2)); // others add(dp[n+1][ng][1][0], v*((n+1)-(ng+1))); } // (n-3, n-1) v = dp[n][ng][1][0]; if (v) { // split n-3, n-1 add(dp[n+1][ng][0][1], v); // adjacent to n-1 add(dp[n+1][ng+1][0][1], v); // split others add(dp[n+1][ng-1][0][0], v*(ng-1)); // others add(dp[n+1][ng][0][0], v*((n+1)-(ng+1))); } // (n-2, n) v = dp[n][ng][0][1]; if (v) { // split n-2, n add(dp[n+1][ng-1][0][0], v); // adjacent to n-1 add(dp[n+1][ng+1][1][1], 2*v); // split others add(dp[n+1][ng-1][1][0], v*(ng-1)); // others add(dp[n+1][ng][1][0], v*((n+1)-(ng+2))); } // none v = dp[n][ng][0][0]; if (v) { // adjacent to n-1 add(dp[n+1][ng+1][0][1], 2*v); // split if (ng > 0) add(dp[n+1][ng-1][0][0], v*ng); // others add(dp[n+1][ng][0][0], v*((n+1)-(ng+2))); } } cout << dp[N][0][0][0] << endl; return 0; }
