けんちょんの競プロ精進記録

競プロの精進記録や小ネタを書いていきます

2-SAT制約

AtCoder ARC 101 F - Robots and Exits (900 点)

またしても、in-place DP のいい練習になった!!! 最初は絶望感が漂うのだけど、これも結局「必要条件を列挙したら十分条件になっていた」系な気もする。 問題へのリンク 問題概要 個のロボットと、 個の穴が一直線上に並んでいる。ロボットは穴に重なると…

AtCoder ARC 085 E - MUL (700 点)

いわゆる「燃やす埋める」の典型 問題へのリンク 問題概要 個の整数 が与えられる (負もある)。今、各 に対して、以下の操作を行うか行わないかを選んで行うことができる。 番目の操作: の倍数であるようなすべての に対して、 の値を 0 にする 操作を行った…