データ構造テク:各値についての結果を予め整理する
AtCoder
ABC-D
AtCoder400点
水色diff
NoviSteps2Q
集計処理
Greedy
Greedy:ある量を決めると残りが決まっていく
データ構造テク:各値についての結果を予め整理する
前処理
連想配列(setやmap)
NP困難(特殊構造なので解ける)
ナップサック
部分和
制約条件:ある値<=K
最適化問題
最大スコア
面白い。各値に対する答えを予め整理して求めておく手法は頻出! 問題へのリンク 問題概要 個の品物がある。品物 は、重さが であり、価値が である。 いくつかの品物を、総和が 以下となるように選ぶとき、選んだ品物の価値の総和の最大値を求めよ。 制約 …