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
上の提出は使っていない変数があるので注意
AtCoderLibrary Lazy-SegmentTree 基礎実装例集
色々実装してみたので、ここに置いておく
対象読者
- 十分な実装時間があれば簡単な機能をもった(例:範囲加算・範囲総和取得など)遅延セグメント木を実装できる
- ATLのlazy_segtreeを使う前に、自分で抽象化されていない簡単な遅延セグメント木を作ってみることを強くおすすめします。
- 抽象化遅延セグメント木特有の考察や、内部実装の理解を前提としたインターフェースが多い為です。
- AtCoderLibrary をコンテスト時間内で読んで分からなかった人向き
全部説明されていなかったら、それは自分の説明力不足です。すみません。
遅延セグメント木を使う上での注意
- 制限に注意。
- うっかり何でも出来ると勘違いしてしまいがちだが、前提を満たさない関数を実装すると、動かない。モノイドとか
- 適切に状態をもたせると、前提を満たす設計が出来るようになる場合がある。本記事では、その例を掲載。
- 遅延セグメント木より汎用性の高い配列型データ構造に平方分割があります。各クエリの計算量がO(sqrt(N))なので注意
- うっかり何でも出来ると勘違いしてしまいがちだが、前提を満たさない関数を実装すると、動かない。モノイドとか
yukicoder No.1171 Runs in Subsequences
yukicoder No.1104 オンライン点呼
概要
- 社員全員はスター型のリモート会議サービスに参加している。お互いの声が聞こえる。
- 遅延があり、社員iは、情報が社員からサーバに届くのにA[i]秒、サーバから社員に届くのにB[i]秒掛かる。
- 社員jは、j-1の数字が聞こえたら or j-2の数字が聞こえてK秒経過したら、jを発声する。
- 社員1が発声してから全員が発声し終わるまでかかる時間
DP
次のような配列を考える。
dp[i] = 社員iが最初に発声する時間
dp[i-1], dp[i-2] の最適解が求まっていれば、dp[i]の最適解も求まる。 前から順に眺めていけば、配列全体の最適解は得られる。
fill(dp, dp+N, inf); long long ans = 0; dp[0] = 0; repeat(i, N) { const auto d = dp[i]; chmax(ans, d); chmin(dp[i + 1], d + A[i] + B[i+1]); chmin(dp[i + 2], d + A[i] + B[i+2] + K); }
社員全員の最初に発声する時間が得られたので、配列の最大値が問題の答えとなる。
計算量はO(N)
AtCoder Beginner Contest 108 - C Triangular Relationship
これ本当に300点ですか???
概要
N 以下の正の整数の組(a, b, c)であって、a+b, b+c, c+a が全てKの倍数であるようなものの個数を求める。
考察
1
%を剰余演算の記号とする。
制約が N <= 2*105なので、aだけを全探索するような実装が予想される。 なので、aを定数と見立てて、b,cのパターンの数を求めるような実装がしたい。
まず、b+cがKの倍数であるようなものについて考察する。 bをx軸、cをy軸に取って、b+cがKの倍数となるような点をマークしていくと、斜めの直線が複数現れると思う。
ここにaの制約を入れたい。a+bがKの倍数なので、bをKで割った余りは(K-a)%K*1でなければならない。 cも同様。
b%K=(K-a)%K となる直線たちと c%K=(K-a)%K となる直線たちを引く。3つの直線が交わる点の個数が、aを固定したときのb,cの個数となる。
実装
int main() { int N, K; scanner >> N >> K; ll ans = 0; iterate(a, 1, N+1) { const int x = K - a%K; if ((x + x)%K != 0) continue; const ll n = (N - x)/K + 1; ans += n*n; } printer << ans << '\n'; return 0; }
いや確かにシンプルですけど…
*1:0以上K未満とする