DP状態:向き
AtCoder
AtCoder400点
ABC-D
緑色diff
二次元グリッド
迷路
DFS
BFS
【問題集】DFS・BFSのステップアップ
グラフ
壁にぶつかるまで動く
DP状態:向き
最大回数・最大個数を求める
グラフの辺数を削減する
グラフの辺数削減テク:頂点に向き情報を付加する
DP状態:直前の場所
グラフの辺数削減テク:うまく並べて隣接する部分のみに辺を張る
壁マス
最適化問題
壁にぶつかるまで動く設定の迷路問題! 問題へのリンク 問題概要 のグリッドがある。各マスは壁 (文字 '#') か通路 (文字 '.') かのいずれかである。グリッドの外周のマスはすべて壁であることが保証されている。 プレイヤーは最初、マス にいる (0-indexed)…
AtCoder
AtCoder500点
ABC-E
水色diff
迷路
二次元グリッド
BFS
0-1BFS
最小回数・最小個数を求める
最短路問題
壁にぶつかるまで動く
グラフの頂点を倍加する
グラフの辺数を削減する
枝刈りBFS
【問題集】DFS・BFSのステップアップ
【問題集】最短路問題
DP状態:向き
グラフの辺数削減テク:頂点に向き情報を付加する
DP状態:直前の場所
グラフの辺数削減テク:うまく並べて隣接する部分のみに辺を張る
壁マス
最適化問題
迷路の最短路問題なので BFS でやりたくなるが、まともにやると で TLE してしまう!! 頂点の持ち方を工夫して 0-1 BFS で解く! 別解として枝刈り BFS も。 drken1215.hatenablog.com 問題へのリンク 問題概要 のグリッドが与えられます。各マスは通路 (文…
AtCoder
AtCoder500点
ABC-E
水色diff
数え上げ問題
DP
二次元グリッド
グリッド上のDP
DP高速化:累積和
累積和
DP高速化
迷路
壁にぶつかるまで動く
賢い漸化式
斜め累積和
経路数の数え上げ
DP状態:向き
DP状態:直前の場所
グラフの辺数削減テク:頂点に向き情報を付加する
グラフの辺数を削減する
DP高速化:直前との比較のみでよい
壁マス
三乗の解法はすぐに出てくるので、それを上手に高速化する! 問題へのリンク 問題概要 のグリッドが与えられる。"." マス (通路) には行けるが "#" マス (壁) には行けない。左上のマスから右下のマスへと行きたい。毎回のターンで以下のいずれかの行動をと…
AOJ
RUPC
迷路
二次元グリッド
最短路問題
DP
盤面を予め変更する
最適化テク:固定する変数を入れ替えて考える
最小コスト
魔法を唱える問題
DP状態:向き
【問題集】最短路問題
典型要素を詰め合わせた教育的問題
壁マス
最適化問題
こういうの超苦手系だけど、苦手なりに解法を詰められたのは成長の証で嬉しい! olphe さん、ナンさんとチームを組んでいて、olphe さんに考察を話して、詰めてくれて、爆弾周りの見落としがあって詰まって、みんなでデバッグして...とチーム戦ならではの考…