kanpurin https://blog.hatena.ne.jp/kanpurin/ かんプリンの学習記録 https://kanpurin.hatenablog.com/ ABC DP高速化 典型 動的計画法 数え上げ 競技プログラミング 解説 問題はこちら 問題概要 解説 提出プログラム 感想 問題概要のチェス盤があり，に白のポーンがある．他にも個の黒のポーンが置かれている．白のポーンはの方向に進むとき，白のポーンがに到達できるようなの数はいくつか．解説を「に到達できるか」とするようなDPを考える．遷移は () (に黒のポーンがある時) (に黒のポーンがない時) となる．このままだととかになるが，黒のポーンがある時の遷移を行う回数は回であり，他のの遷移はDP配列を使いまわすことで無視できる(いわゆるインラインDP)．DP配列の長さがになるが，白のポーンが到達可能な範囲はなので削れる．ソートがネックとなり提出プログラムhttps://… 190 <iframe src="https://hatenablog-parts.com/embed?url=https%3A%2F%2Fkanpurin.hatenablog.com%2Fentry%2F2021%2F05%2F31%2F041904" title="ABC203 E - White Pawn - かんプリンの学習記録" class="embed-card embed-blogcard" scrolling="no" frameborder="0" style="display: block; width: 100%; height: 190px; max-width: 500px; margin: 10px 0px;"></iframe> Hatena Blog https://hatena.blog 2021-05-31 04:19:04 rich https://kanpurin.hatenablog.com/entry/2021/05/31/041904 1.0 100%