前処理
KUPC
AtCoder
大学コンテスト
有志コン
左右からそれぞれ走査する
累積和テク:左右両端からの累積和や累積結果を前処理
Greedy
前処理
場合分け：小さい場合は愚直に解ける
考察：順序を工夫して解く
単純化：操作の流れを単純化して考える
考察：mod3で考える
NoviSteps3D
各kに対して
実装が少し大変だった。そして、両端から Greedy で追い詰めていけばよいのは思いつかなかった。チームメイトが思いついていた。 問題へのリンク 問題概要 1 から までの整数が書かれたカードが合計で 枚あり、整数 の書かれたカードは 枚ある。各 に対して…
AtCoder
AtCoder525点
ABC-F
青色diff
NoviSteps2D
bitDP
前処理
データ構造テク:「次の要素」へのポインタを求める
データ構造テク：indexベースで考える
DP
【問題集】最短路問題
最短路問題
最適化の考察：最適化する対象を入れ替える
最適化問題
最大回数・最大個数を求める
考察：ある数量が小さいことを活用する
部分列
という制約がいかにも怪しい！ 問題へのリンク 問題概要 1 以上 20 以下の整数からなる、長さ の数列 が与えられる。 この数列の部分列 (連続でなくてよい) であって、任意の整数について、その部分列に含まれる個数が 0 個または 2 個であるものを考える。 …
AtCoder
ABC-D
AtCoder400点
水色diff
NoviSteps2Q
集計処理
Greedy
Greedy:ある量を決めると残りが決まっていく
データ構造テク:各値についての結果を予め整理する
データ構造テク：前処理
連想配列(setやmap)
NP困難(特殊構造なので解ける)
ナップサック
部分和
制約条件:ある値<=K
最適化問題
最大スコア
前処理
前処理：個数ごとに最適解を求めておく
面白い。各値に対する答えを予め整理して求めておく手法は頻出！ 問題へのリンク 問題概要 個の品物がある。品物 は、重さが であり、価値が である。 いくつかの品物を、総和が 以下となるように選ぶとき、選んだ品物の価値の総和の最大値を求めよ。 制約 …
