壁にぶつかるまで動く
AtCoder
AtCoder500点
ABC-E
水色diff
数え上げ問題
DP
グリッド
二次元ナップサックDP
DP高速化:累積和
累積和
DP高速化
迷路
壁にぶつかるまで動く
賢い漸化式
「次の要素」へのポインタを求める
三乗の解法はすぐに出てくるので、それを上手に高速化する! 問題へのリンク 問題概要 のグリッドが与えられる。"." マス (通路) には行けるが "#" マス (壁) には行けない。左上のマスから右下のマスへと行きたい。毎回のターンで以下のいずれかの行動をと…
AtCoder
AtCoder700点
AGC-C
黄色diff
f(i,j)をiとjとに分離する
最小回数
Yes/No判定問題
数列
壁にぶつかるまで動く
SをTにすることが目的の操作の問題
操作
条件の言い換え
変数変換して扱いやすい同型な問題を見出す
コーナーケース
DP
DP状態:吸い出しと吸い込み
操作を好きな回数だけ行える
座標圧縮
Greedy
必要条件を列挙したら十分条件になる
いもす法的変換
想定解法とちょっと違うやり方したっぽい 問題へのリンク editorial 問題概要 個のマスが横一列に並んでいる ()。 匹のペンギンがマス にいる。 あなたは,次の操作を好きな回数行うことができる。 ペンギンを 1 匹選び、左または右へ向かって滑らせる ペン…
AtCoder
AtCoder500点
ABC-E
ABC-like
水色diff
壁にぶつかるまで動く
累積max
前処理
個別の要素の動きに注目する
総和を求める
縦に見るものを横に見る
グリッド
数え上げ問題
「次の要素」へのポインタを求める
これを思い出した drken1215.hatenablog.com 問題へのリンク 問題概要 のグリッドが与えられる。あるマスは壁 ('#') になっていて、あるマスは通路 ('.') になっている。通路マスが 個あるとして、すべての「通路マスの部分集合」 ( 通りある) に対して、以…
これも実はよくある典型問題だったりはする。 問題へのリンク 問題概要 下のような の二次元グリッドが与えられる。 #..#.. .....# ....#. #.#... このグリッドで '#' は壁を表している。ここで '.' マスを 1 つ選んで、そこに光源を置きたい。光源が照らす…