2019-12-17から1日間の記事一覧
AtCoder
AtCoder900点
ARC-F
in-place DP
DP
ナップサックDP
BIT
データ構造
DP高速化
DP高速化:セグメント木
区間
区間ソート
探索順序を工夫して解く
条件の言い換え
必要条件を列挙したら十分条件になる
制約条件:2-SAT
座標圧縮
数え上げ問題
コーナーケース
穴や盤外に落とす問題
一直線上のN点の問題
赤色diff
ロボット
操作:一斉に±aする
解空間:O(2^N)通りの選択肢
最適化テク:端点のみを考える
N個の点などを一律に動かす設定の問題
DP高速化:セグメント木上のin-placeDP
またしても、in-place DP のいい練習になった!!! 最初は絶望感が漂うのだけど、これも結局「必要条件を列挙したら十分条件になっていた」系な気もする。 問題へのリンク 問題概要 個のロボットと、 個の穴が一直線上に並んでいる。ロボットは穴に重なると…
きっかけは、タピオカ流競プロ優勝ガール、マリーさんのツイートでした。 100個ぐらいある整数から自由に選んでK円になる組み合わせを探せ!複数通りある場合は列挙!みたいな仕事がだるすぎてdpで列挙してくれるやつ作った競プロは事務員を救う— マリー (@C…
AtCoder
AtCoder300点
ABC-C
バケット
最頻値に関する問題
数列
最適化テク:最適解の形を考える
コーナーケース
緑色diff
ARC-C
second best を管理する
for文
最小回数・最小個数を求める
操作
操作:1文字を変更する
集計処理
最適化問題
意外と罠にはまりやすい問題かもしれない!!! この手の問題は「最適解の形を考える」という意識で解くと良さそう。 そして、コーナーケースがサンプルにあるのが親切。 問題へのリンク 問題概要 長さ ( は偶数) の数列 が /\/\/\/ であるとは 任意の に対…
AtCoder
AtCoder700点
ARC-E
フロー
最小カット
最小カット:PSP(燃やす埋める)
数列
制約条件:2-SAT
グラフ
橙色diff
けんちょん本演習問題
操作
操作:上書き
【問題集】フローのステップアップ
【問題集】フローの入門
解空間:O(2^N)通りの選択肢
そのまま覚えたいシンプル設定の中堅以上の典型問題
中堅以上の典型要素を詰め合わせた教育的問題
マトロイドと劣モジュラ関数
いわゆる「燃やす埋める」の典型です。 問題へのリンク 問題概要 個の整数 が与えられます (負値もありえます)。今、各 に対して、以下の操作を行うか行わないかを選んで行うことができます。 番目の操作: の倍数であるようなすべての に対して、 の値を 0 …