制約条件:2-SAT
面白かった。 問題へのリンク 問題概要 人がいて、それぞれ「スパイ」か「非スパイ」かのどちらかである。 人のうち、何人かについてはスパイかどうかが予めわかっている ( で与えられる)。 個の証言がある。各証言は人 が証言者によってなされ、「人 はスパ…
AtCoder
AtCoder900点
ARC-F
in-place DP
DP
ナップサックDP
BIT
データ構造
DP高速化
DP高速化:セグメント木
区間
区間ソート
探索順序を工夫して解く
条件の言い換え
必要条件を列挙したら十分条件になる
制約条件:2-SAT
座標圧縮
数え上げ問題
コーナーケース
DP高速化:オンラインオフライン変換
穴や盤外に落とす問題
ロボット
一直線上のN点の問題
赤色diff
点が移動していく問題
またしても、in-place DP のいい練習になった!!! 最初は絶望感が漂うのだけど、これも結局「必要条件を列挙したら十分条件になっていた」系な気もする。 問題へのリンク 問題概要 個のロボットと、 個の穴が一直線上に並んでいる。ロボットは穴に重なると…
AtCoder
AtCoder700点
ARC-E
フロー
最小カット
燃やす埋める
数列
制約条件:2-SAT
グラフ問題
橙色diff
けんちょん本演習問題
操作
操作:上書き
負値が本質的に効く問題
いわゆる「燃やす埋める」の典型です。 問題へのリンク 問題概要 個の整数 が与えられます (負値もありえます)。今、各 に対して、以下の操作を行うか行わないかを選んで行うことができます。 番目の操作: の倍数であるようなすべての に対して、 の値を 0 …