DP状態:ナップサック
AtCoder
AtCoder550点
ABC-F
黄色diff
体力や燃料がある一定以上必要になる設定の問題
一直線上のN点の問題
DP
ナップサックDP
操作を逆順に見る
DP状態:ナップサック
最小コスト
解空間:O(2^N)通りの選択肢
制約:数値が10^6以下
最適化問題
少し重たかった。でもいい問題。JOI にありそう。 問題へのリンク 問題概要 数直線上に 箇所の燃料補給所がある。 番目の補給所は次のようになっている。 座標 にある 補給すると、現在の HP が であるとき、HP が になる (コストとして を支払う) 今、高橋…
AtCoder
AtCoder500点
ABC-F
黄色diff
DP
DP状態:ナップサック
累積和
DP高速化
DP高速化:累積和
斜め累積和
数え上げ問題
部分和
絶対値やminを扱う問題
マンハッタン距離
N次元空間
計算幾何
テク:スタートを0としてよい
変数変換して扱いやすい同型な問題を見出す
格子点
ナップサックDP
次元空間という、いかめしいものが出てくるけど、あまり関係ない。DP 高速化が本質。 問題へのリンク 問題概要 次元空間上に 2 つの格子点 , が与えられる。 これらとのマンハッタン距離がともの 以下であるような格子点の個数を 998244353 で割ったあまりを…
AtCoder
AtCoder600点
ABC-F
部分和
DP
ナップサックDP
区間
解空間:O(N^2)通りの選択肢
主客転倒
数え上げ問題
DP状態:フェーズ(耳DP)
青色diff
DP状態:ナップサック
始点と終点がともに動く経路を走査する
ごちゃごちゃとばぐらせながら何とか通した... 問題へのリンク 問題概要 要素の数列 が与えられる。この数列の 通りの区間それぞれについての 区間内の要素の部分集合であって総和が であるものの個数 の総和を求め、998244353 で割ったあまりを求めよ。 制…