2023-07-15から1日間の記事一覧
AtCoder
ACLpractice
二次元グリッド
可視化：二次元情報を二部グラフにして考える
二部グラフ
マッチング
二部マッチング
フロー
そのまま覚えたい典型問題
最小費用流問題
N個からK個を選ぶ設定の問題
順列の最適化問題
順列を題材とした問題
最大スコア
制約条件:K個以下
復元
どれか1つ求める
最適化の考察：変形しても悪化しない
グラフテク:下駄を履かせて負辺除去
フローを流す際にバイパス辺を用意する
解空間:O(N!)通りの選択肢
【問題集】フローの入門
最適化問題
NoviSteps3D
D 問題の MaxFlow に続いて、これまた、人生で一度は解くべき超典型問題ですね。そして、D 問題とは違うやり方で、二部グラフを作ることにも注目です！ 問題へのリンク 問題概要 のグリッドがあり、各マスには数値が書かれています。 これらのマスからいくつ…
AtCoder
ACLpractice
フロー
そのまま覚えたい典型問題
二部グラフ
二次元グリッド
【問題集】フローの入門
市松模様・塗り分け
ドミノ
タイリング
復元
最大流問題
どれか1つ求める
最大回数・最大個数を求める
考察：パリティに着目する
二部マッチング
マッチング
最適化問題
NoviSteps2D
グリッドを市松模様に塗って、「黒色マス」と「白色マス」で二部マッチングするという、超典型問題！ 問題へのリンク 問題概要 のグリッドが与えられます。 各マスは「障害物」が置かれているか、「空」であるかのいずれかです。入力データにおいては、障害…
AtCoder
AtCoder500点
ABC-F
黄色diff
DP
DP状態:ナップサック
累積和
DP高速化
DP高速化:累積和
斜め累積和
数え上げ問題
部分和
絶対値やminを扱う問題
マンハッタン距離
N次元空間
計算幾何
スタートを0としてよい
考察：変数変換
格子点
シーケンシャルDP
次元空間という、いかめしいものが出てくるけど、あまり関係ない。DP 高速化が本質。 問題へのリンク 問題概要 次元空間上に 2 つの格子点 , が与えられる。 これらとのマンハッタン距離がともの 以下であるような格子点の個数を 998244353 で割ったあまりを…
