2019-12-17から1日間の記事一覧
AtCoder
AtCoder900点
ARC-F
in-place DP
DP
ナップサックDP
BIT
データ構造
DP高速化
DP高速化:セグメント木
区間
区間ソート
探索順序を工夫して解く
条件の言い換え
必要条件を列挙したら十分条件になる
制約条件:2-SAT
座標圧縮
数え上げ問題
コーナーケース
DP高速化:オンラインオフライン変換
穴や盤外に落とす問題
ロボット
一直線上のN点の問題
赤色diff
点が移動していく問題
またしても、in-place DP のいい練習になった!!! 最初は絶望感が漂うのだけど、これも結局「必要条件を列挙したら十分条件になっていた」系な気もする。 問題へのリンク 問題概要 個のロボットと、 個の穴が一直線上に並んでいる。ロボットは穴に重なると…
きっかけは、タピオカ流競プロ優勝ガール、マリーさんのツイートでした。 100個ぐらいある整数から自由に選んでK円になる組み合わせを探せ!複数通りある場合は列挙!みたいな仕事がだるすぎてdpで列挙してくれるやつ作った競プロは事務員を救う— マリー (@C…
意外と罠にはまりやすい問題かもしれない!!! この手の問題は「最適解の形を考える」という意識で解くと良さそう。 そして、コーナーケースがサンプルにあるのが親切。 問題へのリンク 問題概要 長さ ( は偶数) の数列 が /\/\/\/ であるとは 任意の に対…
いわゆる「燃やす埋める」の典型 問題へのリンク 問題概要 個の整数 が与えられる (負もある)。今、各 に対して、以下の操作を行うか行わないかを選んで行うことができる。 番目の操作: の倍数であるようなすべての に対して、 の値を 0 にする 操作を行った…