2023-07-24から1日間の記事一覧
AtCoder
ABC-E
水色diff
二次元グリッド
グリッド上のDP
DP
二次元累積和
累積和
二分探索
【問題集】累積和・二分探索法・しゃくとり法
典型要素を詰め合わせた教育的問題
0と1の問題
制約条件:正方形領域
数え上げ問題
解空間:O(N^2)通りの選択肢
極大なものを考える
sparseな問題
ある量を固定して考える
そのまま覚えたい典型問題
単調性に着目する
累積和テク:区間の総和を累積和で高速に求める
【問題集】累積和
【問題集】二次元累積和
【問題集】累積和・いもす法
AtCoder475点
有名な DP をするか、二次元累積和 + 二分探索をするか 問題へのリンク 問題概要 のグリッドが与えられる。グリッドの各マスのうち、指定された 個のマスには穴があいている。その他のマスは穴があいていない。 グリッドに含まれる正方形であって、その内部…
AtCoder
ABC-F
青色diff
DP
DP高速化
DP高速化:累積和
ナップサックDP
DP状態:個数
前処理
数え上げ問題
操作
操作:上書き
ダブルカウントを防ぐ場合分け
操作によって作れるものの集合を考える(判定関数を考える)
操作後の結果の数え上げ
伝播していく様子をテーマにした問題
二次元グリッド
0と1の問題
操作を好きな回数だけ行える
AtCoder525点
最初、各マスをタスクに見立てて、タスクの依存関係を考える DAG 上で DP できないかなどと考えたけど、うまくいかなかった。普通にグリッドを左から舐めていく DP でよかった! 問題へのリンク 問題概要 のグリッドがある。各マスはすでに白色 (文字 '.') …
AtCoder
AtCoder400点
ABC-D
緑色diff
二次元グリッド
迷路
DFS
BFS
【問題集】DFS・BFSのステップアップ
グラフ
壁にぶつかるまで動く
DP状態:向き
最大回数・最大個数を求める
グラフの辺数を削減する
グラフの辺数削減テク:頂点に向き情報を付加する
DP状態:直前の場所
グラフの辺数削減テク:うまく並べて隣接する部分のみに辺を張る
壁マス
最適化問題
壁にぶつかるまで動く設定の迷路問題! 問題へのリンク 問題概要 のグリッドがある。各マスは壁 (文字 '#') か通路 (文字 '.') かのいずれかである。グリッドの外周のマスはすべて壁であることが保証されている。 プレイヤーは最初、マス にいる (0-indexed)…
Functional グラフのサイクル検出問題! 問題へのリンク 問題概要 頂点数 のグラフが与えられる。頂点 からは頂点 への辺が接続していて、辺数は全部で 本ある。 このグラフにおいて、同一頂点を複数回含まない有向サイクルをひとつ求めてください。具体的に…