ABC015D 解法 ナップザック問題の DPと同じで，部分和問題の DP. 状態数が少ない様に DP の定義域と値域を選ぶと， 空間計算量と時間計算量が小さくできる． 使っている記号，マクロ等 "https://ecsmtlir.hatenablog.com/entry/2022/12/23/131925" int main(…

ABC019D 解法 木の直径を求めるアルゴリズム． 任意に頂点を選び，\(v_{0}\) とする． \(v_{0}\) から最も遠い点の一つを \(v_{1}\) とする． \(v_{1}\) から最も遠い点の一つを \(v_{2}\) とする． \(v_{1}, v_{2}\) が直径の一つ． 実装 始点を固定したと…

解法 2人のプレイヤーの座標の組を頂点にもつグラフ上でBFS． 実装 移動先の位置は，今のマスにも依存することに注意． 壁に向かって移動しようとしたときは，今の位置にとどまるが， もう一方のプレイヤーが移動できる場合がある． 使っている記号，マクロ…