競プロ典型90問難易度7
AtCoder
競プロ典型90問
競プロ典型90問とその類題
競プロ典型90問難易度7
最小カット:PSP(燃やす埋める)
最小カット
【問題集】フローのステップアップ
【問題集】フローの入門
フロー
解空間:O(2^N)通りの選択肢
鍵やアイテムを題材とした問題
最大スコア
最適化問題
Project Selection がピッタリハマる問題！ 問題へのリンク 問題概要 個の家 がある。家 に入るためには のコストがかかるが、その代わり の利得が得られる。また、各家 に対して、次の 個の制約条件が付随している。 家 に入ることなくして、家 に入ること…
AtCoder
競プロ典型90問
競プロ典型90問とその類題
競プロ典型90問難易度7
フロー
【問題集】フローの入門
二部グラフ
二部マッチング
マッチング
二次元平面上のN点の問題
復元
Yes/No判定問題
見積り大事
sparseな問題
遷移先が限られる
二部マッチングの練習問題 問題へのリンク editorial へのリンク 問題概要 二次元平面上に 体の飛行機がある。飛行機 は座標 にいる。各飛行機に対して適切に 8 種類の向き付けをしたい (上・下・左・右・左上・左下・右上・右下)。 具体的には、 秒後におい…
競プロ典型90問
AtCoder
競プロ典型90問とその類題
競プロ典型90問難易度7
漸化式
DP
行列
行列累乗
ダブリング
整数を「10倍してaを足す」で捉える
DP状態:あまり
sparseな問題
DP高速化:FFT
FFT
DP高速化:きたまさ法・Bostan-Mori法
数え上げ問題
DP高速化:ダブリング
DP状態:どの桁まで見たか(広義の桁DP)
きたまさ法によく似たタイプの DP ダブリング高速化！ ただかなり難しい問題だと思うので、004 まで順調に解いていた方が、この問題で挫折しないように注意！！！ 無理に解こうとせずに飛ばすのも一案だと思います...... 問題へのリンク editorial 問題概要 …
