2017-10-04

競技プログラミングにおける連結DP問題まとめ

競技プログラミング

連結DP

造語なのだが、連結性を状態として持つDP
フロンティア法とかとも言う

問題

2017-10-04

競技プログラミングにおける挿入DP問題まとめ

競技プログラミング

挿入DP

順列などに挿入することで遷移を進めていくDP

挿入DPとは逆に抜いていくDP（抜去DP）

ARC097 Sorted and Sorted 解説

【発展的話題】挿入DPの更新最適化

挿入DPの時に掛け算を遅延評価して、上手くやる

rep(i, 0, N) rep(k, 0, N) rep(col, 0, N) {
    dp[i + 1][k][col] = dp[i][k][col] * (k + 1);
    if(c[i] == col) dp[i + 1][k][c[i]] += dp[i][k][col];
    else dp[i + 1][k + 1][c[i]];
}

を掛け算を遅延評価することでO(N^3)からO(N^2)へ削減可能

これ解説1 解説2 解説3

2017-10-04

競技プログラミングにおけるUnionFind問題まとめ [DSU]

競技プログラミング

UnionFind, DSU

連結成分を管理するデータ構造 (解説)
AtCoder Libraryで実装がある
最小全域木の構成でも使われる
連結時に成分に入っている情報を併合することもある(要素数とか)
incremental(併合はできるが、分離はできない)
(発展だが)永続UnionFindもある
森の連結成分は「頂点数-辺数」で求められるテクがある
ダブリングを用いることで連続区間のマージができるようになる問題1 問題2

問題

AtCoder Union Find

連結判定

連結判定+データ

永続UnionFind

AGC002 Stamp Rally (永続UnionFind解だとTLEするかも)

森の連結成分は「頂点数-辺数」で求められるテク

【発展的話題】 Dynamic Connectivity

参考
セグメント木を2つ持ってセグメント木上でDFSするらしいがさっぱり分からん
動的木でそれっぽいことできるのでは？
CFの記事
【競技プログラミング】online dynamic connectivity(削除可能union-find)の作り方を詳しく解説！！！ - Qiita この前見つけた。ちゃんと読んでない

問題

2017-10-03

競技プログラミングにおけるマンハッタン距離問題まとめ

競技プログラミング

マンハッタン距離

マンハッタン距離(wiki)
最強のマンハッタン距離解説記事
テク
- 45度回転
  - 参考
  - 全ての座標を(x,y)から(x+y,x-y)で変換する
  - すると、あるマンハッタン距離dで移動可能な範囲は正方形の形になる
  - 回転前のマンハッタン距離 = 回転後のチェビシェフ距離（座標の差の最大値）
- 差の総和を最小化するときは中央値を使う
- ある2点のマンハッタン距離は同じ回転移動・平行移動を施しても同じになる Let's Dance!(hard) | EEIC Programming Contest #1 Question | Contests | HackerRank