始点と終点がともに動く経路を走査する
AtCoder
AtCoder600点
ABC-Ex
橙色diff
DP状態:フェーズ(耳DP)
始点と終点がともに動く経路を走査する
解空間:O(N^2)通りの選択肢
平方分割
考察：場合分けして考える
二次元グリッド
多項式・FPS(形式的冪級数)
DP
グリッド上のDP
opt さんとのスペースで解いた！ いくつか典型を見落としていたのでメモ！！ 問題へのリンク 問題概要 のグリッドがあって、マス には値 が記されている。 いずれかのマスから始めて右または下に隣接するマスへの移動を 0 回以上繰り返すことで得られる経路…
AtCoder
AtCoder600点
ABC-F
部分和
DP
シーケンシャルDP
区間
解空間:O(N^2)通りの選択肢
考察：主客転倒・寄与分解
数え上げ問題
DP状態:フェーズ(耳DP)
青色diff
DP状態:ナップサック
始点と終点がともに動く経路を走査する
ごちゃごちゃとばぐらせながら何とか通した... 問題へのリンク 問題概要 要素の数列 が与えられる。この数列の 通りの区間それぞれについての 区間内の要素の部分集合であって総和が であるものの個数 の総和を求め、998244353 で割ったあまりを求めよ。 制…
AtCoder
AtCoder400点
水色diff
ABC-D
DP
グリッド上のDP
二次元グリッド
解空間:O(N^2)通りの選択肢
始点と終点がともに動く経路を走査する
マンハッタン距離
最小コスト
テク:reverse/rotateしてもう一回やる
考察：場合分けして考える
場合分け：2点や2区間の配置関係を考える
考察：一部の変数を固定して考える
考察：操作・条件・目的関数を言い換える
最適化問題
結構アドホックな感覚が必要な DP で難しいと思う！ 緑色よりは上の色だろうと思ったら、案の定水色上位だった。 問題へのリンク 問題概要 のグリッドが与えられ、各マス には値 が書かれている。 グリッドから異なる 2 マス を選ぶとする。その 2 マスのス…
