max(pi-pj,0)
AtCoder
AOJ
Greedy
Greedyなマッチング
N個のものうち1個を変更・削除したものを解く
累積和テク:左右両端からの累積和や累積結果を前処理
累積max
累積和
マッチング
二部マッチング
JOI
JOI本選
JOI難易度6
各kに対して
数列
最適化テク:解を変形していく(最適性を失わずに)
max(pi-pj,0)
累積和テク:累積和や累積結果を前処理しておく
ソート:前処理
まずソートして考える
Greedy を考察して、さらに左右から累積和を求める!結構難しい! 問題へのリンク editorial 類題とか drken1215.hatenablog.com 問題概要 長さ の数列 と、長さ の数列 が与えられます。各 に対して、次の値を求めよ。 数列 から を除去してできる長さ の数…
AtCoder
AtCoder500点
ARC-C
最短路問題
牛ゲー
双対性
最長路問題
順列の最適化問題
DP
差分制約系
グラフ
前処理
指数探索系問題
ある量を固定して考える
青色diff
区間
固定長区間が制約条件を持ちながら左右に移動する問題
必要条件を列挙したら十分条件になる
条件の言い換え
累積max
一直線上のN点の問題
個人的要復習
max(pi-pj,0)
【問題集】最短路問題
思わず解きたくなる興味深い良問
隣接2要素に制約や目的関数のある問題
難しかった 問題へのリンク 問題概要 体重が であるような 体のラクダがいる。ラクダを一列に並べる方法のうち、次の条件を満たすものについて、左端のラクダと右端のラクダの距離として考えられる最小値を求めよ。また、そのようにラクダを並べることが不可…
グラフ
全探索
Union-Find
重み付きUnion-Find
データ構造
コーナーケース
IP定式化
AOJ
差分制約系
AOJ-ICPC
AOJ-ICPC800点
JAG
JAG夏合宿
牛ゲー
max(pi-pj,0)
双対性
テーマにストーリー性のある面白い問題
現実世界の題材を扱った問題
「全探索でもここまで難しいやつもある」という例としてよく挙げられる問題。 ここのページに僕なりの 全探索 重み付き Union-Find 木を使いながら判定 をした解法を記した。