AtCoder575点
AtCoder
AtCoder575点
ABC-G
黄色diff
DP
区間DP
DP状態:吸い出しと吸い込み
DP値を利用して状態復元
入れ子構造
文字列
操作
操作を好きな回数だけ行える
操作:削除
操作後の結果の最適化問題
最大スコア
操作:区間
最適化問題
o......f...(.....)... のようなパターンで、(.....) の中身が消せるような場合を最初見落とした。 問題へのリンク 問題概要 長さ の文字列 に対して、次の操作を好きな回数だけ行える。操作後の文字列の長さとして考えられる最小値を求めよ。 が連続する部…
AtCoder
ABC-F
黄色diff
ギリギリ
最適化テク:探索候補を絞る
最適化テク:端点のみを考える
一直線上のN点の問題
数え上げ問題
座標圧縮
平面走査
Greedy
マッチング
二部マッチング
区間
固定長区間が制約条件を持ちながら左右に移動する問題
AtCoder575点
高速な解法もあるっぽいけど、愚直に解いた。 問題へのリンク 問題概要 一直線上に 個の宝が座標 に配置されている。一方、長さが である 本の棒がある。次の条件を満たす整数 の個数を求めよ。 各 に対して、座標 の点を始点とするように棒を置いたとき、棒…
AtCoder
ABC-G
黄色diff
グラフ
フロー
【問題集】フローのステップアップ
【問題集】フローの入門
最大パッキングを求める
パッキング
グラフのconnectivity
頂点に容量があるフロー
Yes/No判定問題
中堅以上の典型要素を詰め合わせた教育的問題
AtCoder575点
点素パスのパッキング系の問題、出ないな〜〜と思っていたら出た！ 問題へのリンク 問題概要 頂点数 、辺数 の単純無向グラフが与えられる。3 頂点 が指定される。 2 頂点 を端点とする単純パスであって、頂点 を通るものが存在するかどうか判定せよ。 制約 …
AtCoder
黄色diff
ABC-G
スライド最小値
Cartesian木
ある量を固定して考える
制約:数値が10^6以下
ヒストグラム内の極大長方形の列挙
stack
左右からそれぞれ走査する
二次元グリッド
最大スコア
制約条件:長方形領域
縦方向と横方向の情報を整理する
前処理
絶対値やminを扱う問題
極大なものを考える
そのまま覚えたいシンプル設定の中堅以上の典型問題
区間
最大値や最小値に着目する
ヒストグラム
AtCoder575点
操作をstackを用いて高速化する
最適化問題
黒マスを避けながら、長方形領域の値の総和を最大化する問題として解いた！ 問題へのリンク 問題概要 のグリッドがあって、各マス には正の整数 が書かれている。 グリッドに含まれる長方形領域のうち、「長方形領域に含まれる値の総和」と「長方形領域に含…
