DP値:二値
Codeforces
場合分け
2^K
添字のとりうる範囲がlogオーダー
Dijkstra法
最短路問題
DP値:二値
DP
グラフ問題
操作:辺の向きをflip
グラフの頂点を倍加する
パリティ
コーナーケース
2回やる意味はない
CodeforcesDIV1-C
CodeforcesR2400
AOJ-ICPC みを感じる！ 問題へのリンク 問題概要 頂点数 、辺数 の有向グラフが与えられる。頂点 1 から頂点 へとたどり着きたい。以下の 2 種類の操作ができる。 頂点 上にいるとき、辺 をたどって、頂点 へと移動する 移動に要するコストは 1 任意の頂点に…
AtCoder
AtCoder500点
ABC-E
Greedy
各kに対して
補集合を考える
DP値:二値
累積和
左右両端からの結果を前処理
前処理
N個のものうち1個を変更・削除したものを解く
青色diff
発想は AtCoder ABC 125 C - GCD on Blackboard (300 点) AtCoder ARC 074 D - 3N Numbers (500 点) とかに似てる。 問題へのリンク 問題概要 長さ の o と x で構成された文字列 が与えられる。 の index から 個選ぶ方法のうち 選んだ index はすべて o で…
AtCoder
AtCoder500点
Greedy
固定する変数を入れ替えて考える
Dijkstra法
DP値:二値
DP
Floyd-Warshall法
最短路問題
燃料補給系問題
グラフ問題
密グラフ
今が良いほど未来も良いGreedy
前処理
クエリ処理問題
青色diff
この Floyd--Warshall は天才すぎる！ 問題へのリンク 問題概要 頂点 辺の重み付き無向単純グラフが与えられる。容量 の燃料タンクがあって、長さ の辺を通ると、タンクの燃料残量が だけ減少する。 各頂点では燃料を補給できて、補給すると満タン (容量 の…
最長増加部分列 (LIS) がセグ木上のインライン DP で求められることを思い出せば、それを少し頑張るとできる。 問題へのリンク 問題概要 長さ の数列 が与えられる。数列 の最長増加部分列 (狭義単調増加) のうち、その総和の最大値を求めよ。 制約 考えたこ…
