2019-02-03から1日間の記事一覧
各桁ごとに見る
XOR
DP状態:smaller(桁DP)
制約条件:総和<=K
Greedy
ある量を固定して考える
ある量を決めるとGreedy
ABC-D
AtCoder400点
AtCoder
水色diff
どの場所で初めてsmallerになるかを考える
DP状態:どの桁まで見たか(広義の桁DP)
制約条件:ある値<=K
以下の典型思考で解けるけど、苦手意識...^^; XOR な問題は各桁ごとに見る の動ける範囲が 以下と指示されているときは、 を上位ビットから見ていったときに、それがどこまで と一致するかを考える (桁 DP でおなじみの考え方) 問題へのリンク 問題概要 個の…
ソート
Greedy
ABC-C
AtCoder300点
区間
最適化テク:解を変形していく(最適性を失わずに)
AtCoder
補集合を考える
一直線上のN点の問題
茶色diff
最小コスト
点が移動していく問題
最短路問題
【問題集】最短路問題
駒(コマ)や石やコインを扱う問題
被覆
N個の区間の問題
Greedy:条件を満たすまで大きい順に取っていく
最適化問題
ソートする問題。 問題へのリンク 問題概要 個のコマを数直線上に配置して、それぞれ移動させる。 それによって、 個の地点 をすべて訪れるようにしたい。総移動距離の最小値を求めよ。 制約 考えたこと とりあえず、各コマについて、「行って、引き返して」…
