グリッド上の最短経路の数え上げをする DP。鉄則本の問題なので、コードのみ。 問題へのリンク 問題概要 のグリッドがあり、各マスは壁または通路である。左上マスと右下マスは通路である。 左上マスから右下マスへと、右方向と下方向の移動のみを繰り返し、…

DP の典型問題だけど、最初は難しく感じるかもしれない。あと、縦横が微妙に混乱するね。 問題へのリンク editorial 問題概要 (今風に表現改) のグリッドが与えられる。このグリッドで上から 番目、左から 番目のマスを と書くことにする。最初、マス に駒が…

有名な DP をするか、二次元累積和 + 二分探索をするか 問題へのリンク 問題概要 のグリッドが与えられる。グリッドの各マスのうち、指定された 個のマスには穴があいている。その他のマスは穴があいていない。 グリッドに含まれる正方形であって、その内部…

慣れないと頭がごっちゃになるけど、一度慣れればもう機械的に解ける系！！ 問題へのリンク 問題概要 のグリッドがある。各マスには '+' か '-' のいずれかの文字が書かれている。 最初、左上マスにコマが置かれている。高橋君と青木君は交互に、次の操作を…

opt さんとのスペースで解いた！ いくつか典型を見落としていたのでメモ！！ 問題へのリンク 問題概要 のグリッドがあって、マス には値 が記されている。 いずれかのマスから始めて右または下に隣接するマスへの移動を 0 回以上繰り返すことで得られる経路…

三乗の解法はすぐに出てくるので、それを上手に高速化する！ 問題へのリンク 問題概要 のグリッドが与えられる。"." マス (通路) には行けるが "#" マス (壁) には行けない。左上のマスから右下のマスへと行きたい。毎回のターンで以下のいずれかの行動をと…

最初、同じ行の「連続する 3 個」しか選べないのだと誤読してしまった... 問題へのリンク 問題概要 二次元座標平面上で、(1, 1) から (R, C) へと格子点を辿って最短経路で進みたい (上か右にしか行けない)。 K 個の座標 () に価値 のアイテムがある。通った…

結構アドホックな感覚が必要な DP で難しいと思う！ 緑色よりは上の色だろうと思ったら、案の定水色上位だった。 問題へのリンク 問題概要 のグリッドが与えられ、各マス には値 が書かれている。 グリッドから異なる 2 マス を選ぶとする。その 2 マスのス…