2018-05-30から1日間の記事一覧
ある量を固定して考える
Greedy
操作
最大値と最小値の差を扱う問題
ARC-E
AtCoder
AtCoder600点
ある量を決めるとGreedy
最大値や最小値に着目する
数列
区間
操作後の結果の最適化問題
青色diff
ARC 098 E Range Minimum Queries 問題概要 長さ N の数列 A と整数 K が与えられる。 この配列に、以下の操作を Q 回行います。 長さ K の連続する部分列を 1 つ選ぶ。 そして、選んだ部分列に含まれる K 個の要素のうち最小のもの(複数ある場合はその中で…
累積和
AtCoder300点
AtCoder
ABC-C
茶色diff
最適化テク:最適解の形を考える
前処理
累積和テク:左右両端からの累積和や累積結果を前処理
N個のものうち1個を変更・削除したものを解く
ARC-C
そのまま覚えたい典型問題
累積和テク:累積和や累積結果を前処理しておく
DP
DP状態:フェーズ(耳DP)
ナップサックDP
DP状態:on/off
0と1の問題
累積和テク:条件を満たすものの個数を累積和で表す
典型要素を詰め合わせた教育的問題
【問題集】累積和
累積和の典型問題 問題へのリンク 問題概要 WWEWEEWWEE のような文字列が与えられる。 文字列のうちの 1 つの文字を選んで、その左側をすべて E に、右側をすべて W にするのに必要な変更量の最小値を求めよ。 制約 解法 累積和を用いる。 #include <iostream> #includ</iostream>…