斜め累積和
AtCoder
AtCoder500点
ABC-F
黄色diff
DP
DP状態:ナップサック
累積和
DP高速化
DP高速化:累積和
斜め累積和
数え上げ問題
部分和
絶対値やminを扱う問題
マンハッタン距離
N次元空間
計算幾何
テク:スタートを0としてよい
変数変換して扱いやすい同型な問題を見出す
格子点
シーケンシャルDP
次元空間という、いかめしいものが出てくるけど、あまり関係ない。DP 高速化が本質。 問題へのリンク 問題概要 次元空間上に 2 つの格子点 , が与えられる。 これらとのマンハッタン距離がともの 以下であるような格子点の個数を 998244353 で割ったあまりを…
AtCoder
AtCoder500点
ABC-E
水色diff
数え上げ問題
DP
二次元グリッド
グリッド上のDP
DP高速化:累積和
累積和
DP高速化
迷路
壁にぶつかるまで動く
賢い漸化式
斜め累積和
経路数の数え上げ
DP状態:向き
DP状態:直前の場所
グラフの辺数削減テク:頂点に向き情報を付加する
グラフの辺数を削減する
DP高速化:直前との比較のみでよい
壁マス
三乗の解法はすぐに出てくるので、それを上手に高速化する! 問題へのリンク 問題概要 のグリッドが与えられる。"." マス (通路) には行けるが "#" マス (壁) には行けない。左上のマスから右下のマスへと行きたい。毎回のターンで以下のいずれかの行動をと…