ABC179D
しばらく悩んで、飛ばしてEへ
悩み「え、これ範囲が広いと困るのでは？」←正しい
素朴にメモ化再帰DPで書いてみて案の定TLE
小さい方からループで塗りつぶすDPにしてもTLE
でもそのコードを見て「あ、要するにこの最内ループを潰せばいいんだな」と気づく
少し綺麗にしたコード
pythondef solve(N, K, SS):
count = [0] * (N + 10)
count[0] = 1
accum = [0] * (N + 10)
accum[0] = 1
for pos in range(1, N):
ret = 0
for left, right in SS:
start = pos - right - 1
end = pos - left
ret += (accum[end] - accum[start])
ret %= MOD
count[pos] = ret
accum[pos] = accum[pos - 1] + ret
ret = count[N - 1]
return ret % MODTwitter見てたら「いもす法だ」とか言ってる人がいたけど、そうかな。僕はそういう意識はなかった。
DPの計算をする上で範囲の和を計算する部分が、範囲が広い時に「たくさんの数を足し合わせる」になって遅いのが解決すべき問題
そこで「今までに計算した数の和」の配列を別途作ってやる
これは「新しい値を前の値に足す」で作れる
これを累積和と言ってる
いざ広い範囲の和が必要になった時には、範囲終了点での累積和から範囲開始点の一つ手前の累積和を引けば得られる
Twitter見てたらセグメント木だと言ってる人もいる
セグメント木は範囲和がO(logN)なので、ループで回して和を計算するO(N)よりは速くなる
今回使った累積和はO(1)なのでさらに速い
累積和は先頭からしか値を入れられないが、セグメント木では任意の位置に入れられる。この柔軟性の分だけ遅いと言えるだろう。
今回は先頭からDPするので任意位置に入れられる必要はなかった。
Related Pages
- →#×共同化×s-pdca×納得感のない計画×##×双対セグメント木×時間がない×🤖2023-08-12_02:30×ABC179×依頼を先延ばしにする症例×ppoi×agc032b×hatena2009-04-26×「ボードゲームとしてのクリーンランゲージ」とは×hatena2009-05-14×初つぶやきglsl→
- →数え上げ×degwer×状態をまとめる×dpは全探索の高速化×arc059f×codefestival_2016_final_f×aoj2439×探索順の変更×大きい順に並べる×aoj2333×順列は挿入dp×bit_dp×区間は終点でソート×条件の言い換え×操作は多いが産物は少ない×agc013d×線形和への分解×演算順序の変更×ビット演算を桁ごとに分解×部分群×操作が可逆で全域→部分群×ラグランジュの定理×再帰的定義→dp×arc037d×桁dp×aoj0570×累積和×フェニック木×高速フーリエ変換×ntt×高速ゼータ変換×and_と_add_の畳み込み×二分累乗×agc013e×行列木定理×全域木の個数×lgv公式×非交叉経路の個数×小さい確率を無視する×二項係数の公式×経路数×45度回転×xとyにわける×カタラン数×包除原理×agc005d×約数系包除×arc064f→
- →オイラー路×グリッド上の幅優先探索×ハンガリアン法×二部グラフの最大マッチング×二重辺連結成分分解×二重頂点連結成分分解×全点対間最短路×単一始点最短路×強連結成分分解×彩色数×最大クリーク×最大流×最大独立集合×最小全域有向木×最小全域木×最小流量制限付き最大流×最小費用流×橋/関節点×bit×binary-trie×convex-hull-trick-add-monotone×li-chao-tree×link-cut木_部分木クエリ×link-cut木×ウェーブレット行列×スパーステーブル×スライド区間の昇順k個の和×セグメント木×トライ木×マージ可能ヒープ×列の平方分割×平衡二分探索木×永続配列×素集合データ構造×unionfind×ローリングハッシュ×接尾辞配列×最長共通接頭辞×最長回文×回文×複数文字列検索×hl分解×全方位木dp×最小共通祖先×木の直径×木の重心分解×根付き木に変換×mod-pow×オイラーのφ関数×オイラーのφ関数テーブル×ベル数×ラグランジュ補間×二項係数×二項係数テーブル×任意mod畳み込み×分割数×分割数テーブル×商列挙×形式的冪級数×形式的べき級数×拡張ユークリッドの互除法×拡張ユークリッド互除法×第2種スターリング数×約数列挙×素因数分解×素数テーブル×素数判定×組合せ×行列演算×進数変換×階乗×離散対数問題×高速フーリエ変換×divide-and-conquer-optimization×monotone-minima×スライド最小値×一次元累積和×二次元累積和×個数制限付きナップサック×最大長方形×最適二分探索木×最長増加部分列×ダブリング×包除原理×燃やす埋める問題×燃やす埋める×牛ゲー×mo’s_algorithm×offline-dynamic-connectivity×座標圧縮×アルゴリズム→
- →アルゴリズム×蟻本×区間スケジューリング×二分探索木×unionfind×最短路問題×最小全域木×ユークリッドの互除法×ニ分探索×しゃくとり法×半分全列挙×座標圧縮×セグメント木×binary_lndexed_tree×バケット法×平方分割×ビットdp×bitdp×行列累乗×繰り返し二乗法×最大流×最小カット×二部マッチング×一般マッチング×マッチング×辺カバー×安定集合×点カバー×最小費用流×凸包×grundy数×強連結成分分解×2-sat×lca×ダブリング×接尾辞配列×Sparse Table×rmq×atcoder→
- →交叉半束×結合法則×交換法則×冪等性×セグメント木×スパーステーブルとセグメント木×最小共通祖先×オイラーツアー×range_minimum_query×2d_sparse_table×2d_range_minimum_query×スパーステーブル→
- →atcoder×atcoder_library_practice_contest×numba×cython×フェニック木×セグメント木×遅延伝搬セグメント木×接尾辞配列×lcp_array×pythonでの累乗・逆数・階乗・階乗逆数・組み合わせ×中国剰余定理×floor_sum×np.convolve×two_snuke×長整数が速い×dsu×unionfind×最大流×最小費用流×scc×2-sat→
"Engineer's way of creating knowledge" the English version of my book is now available on [Engineer's way of creating knowledge]
(C)NISHIO Hirokazu / Converted from [Scrapbox] at [Edit]