yukicode No.1513 simple 門松列 problem
最近この手の記事を書いていないので書く。この問題は、多段階の考察が必要。
問題
(0...K) から構成される数列のうち、門松列列を満たすものの個数を求めよ。ついでに含まれている数の総和を求めよ。
考察
めんどくさいので、以降門松列列を🎍と呼ぶ。
0
総和の計算は難しいので一旦忘れる。まずは数え上げをする。
1
よくある動的計画法。🎍を満たす数列に整数を末尾に加えた数列が🎍を満たしているかどうかは、2つ前の値と今追加した値を見れば判定が出来る。 だから、2つ前の値をパラメータに持つ動的計画法をやる。
つまり、dp1[c][i][j] := 1つ前の値がjで2つ前の値がiであるような長さc+2の数列のうち🎍を満たす数列の個数 と定義したdp1を計算する。
長さ2(c=0)の時は、dp1[0][i][j] = i==j と定義すると、若干楽出来る。
最終的に求めたい「門松列列を満たすものの個数」は、dp1[N-2][i][j] (i=0...K, j=0...K) の総和を取れば良い。
repeat(i, K) {
repeat(j, K) {
dp1[0][i][j] = i != j;
}
}
repeat(c, N-2) {
repeat(i, K) {
repeat(j, K) {
repeat(k, K) {
if (kado(i,j,k)) {
dp1[c+1][j][k] += dp1[c][i][j];
dp1[c+1][j][k] %= MD;
}
}
}
}
}
ll total1 = 0;
repeat(i, K) {
repeat(j, K) {
total1 += dp1[N-2][i][j];
}
}
total1 %= MD;
時間計算量はO(NK3)。最悪ケースで10秒ぐらい掛かるので、4重ループを改善したい。
2
このような、単純なループは、ループ順序を並びかえることが出来る場合がある。 入れ替えても問題無さそうなので、並び替えてみる。
repeat(c, N-2) {
repeat(j, K) {
repeat(k, K) {
repeat(i, K) {
if (kado(i,j,k)) {
dp1[c+1][j][k] += dp1[c][i][j];
dp1[c+1][j][k] %= MD;
}
}
}
}
}
iを内側にしてみた。dp1の参照にiは使っていないので、なんかうまいこと計算すればiのループを無くせそうなお気持ちが湧いてくる。
3
iのループを無くせそうだが、🎍判定関数 kado(i,j,k) がこれを阻害している。展開しよう。
repeat(c, N-2) {
repeat(j, K) {
repeat(k, K) {
repeat(i, K) {
if ((i!=k)&&((i<j&&j>k)||(i>j&&j<k))) {
dp1[c+1][j][k] += dp1[c][i][j];
dp1[c+1][j][k] %= MD;
}
}
}
}
}
数式の式変形と同じことをしていく。🎍判定関数の、iに依存しない比較ならiのループ外に出せるはず。orは、以下のように実装を重複させれば展開出来る。
repeat(j, K) {
repeat(k, K) {
if (j > k) {
repeat(i, K) {
if ((i!=k)&&(i<j)) {
dp1[p2][j][k] += dp1[p1][i][j];
dp1[p2][j][k] %= MD;
}
}
}
else if (j < k) {
repeat(i, K) {
if ((i!=k)&&(i>j)) {
dp1[p2][j][k] += dp1[p1][i][j];
dp1[p2][j][k] %= MD;
}
}
}
}
}
repeat(i, K) の中に (i<j) があるということは、repeat(i, j) のように出来るはず。
repeat(j, K) {
repeat(k, K) {
if (j > k) {
for (int i = 0; i < j; ++i) {
if (i != k) {
dp1[p2][j][k] += dp1[p1][i][j];
dp1[p2][j][k] %= MD;
}
}
}
else if (j < k) {
for (int i = j+1; i < K; ++i) {
if (i != k) {
dp1[p2][j][k] += dp1[p1][i][j];
dp1[p2][j][k] %= MD;
}
}
}
}
}
(i != k) については、後から(i == k)の値を引けば良いです。
repeat(j, K) {
repeat(k, K) {
if (j > k) {
for (int i = 0; i < j; ++i) {
dp1[p2][j][k] += dp1[p1][i][j];
dp1[p2][j][k] %= MD;
}
dp1[p2][j][k] -= dp1[p1][k][j] + MD;
dp1[p2][j][k] %= MD;
}
else if (j < k) {
for (int i = j+1; i < K; ++i) {
dp1[p2][j][k] += dp1[p1][i][j];
dp1[p2][j][k] %= MD;
}
dp1[p2][j][k] -= dp1[p1][k][j] + MD;
dp1[p2][j][k] %= MD;
}
}
}
シンプルになった。dp1[p1][i][j] は k に依存しないので、kのループの外側で計算することが出来るはず。
repeat(j, K) {
ll sum1 = 0;
for (int i = 0; i < j; ++i) {
sum1 += dp1[p1][i][j];
sum1 %= MD;
}
ll sum2 = 0;
for (int i = j+1; i < K; ++i) {
sum2 += dp1[p1][i][j];
sum2 %= MD;
}
repeat(k, K) {
if (j > k) {
dp1[p2][j][k] += sum1;
dp1[p2][j][k] %= MD;
dp1[p2][j][k] -= dp1[p1][k][j] + MD;
dp1[p2][j][k] %= MD;
}
else if (j < k) {
dp1[p2][j][k] += sum2;
dp1[p2][j][k] %= MD;
dp1[p2][j][k] -= dp1[p1][k][j] + MD;
dp1[p2][j][k] %= MD;
}
}
}
k のループの下にはループが無くなり、全体の時間計算量は $O(NK2)$ になりました。
4
数列の合計も上記と同様に計算できます。先程の「🎍を満たすものの個数」の計算結果を利用することに気づけないと、ここではまると思います。
冗長になりそうなので省略。
提出
#669259 (C++14) No.1513 simple 門松列 problem - yukicoder
上の提出は使っていない変数があるので注意
