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