中堅以上の典型要素を詰め合わせた教育的問題
しゃくとり法
考察：一部の変数を固定して考える
全探索
変数固定：3つのうちの真ん中
数列
データ構造テク：前処理
二分探索
累積和
最大値と最小値の差を扱う問題
ABC-D
AtCoder
AtCoder600点
累積和テク:左右両端からの累積和や累積結果を前処理
青色diff
ARC-D
均等に分ける
そのまま覚えたいシンプル設定の中堅以上の典型問題
中堅以上の典型要素を詰め合わせた教育的問題
3つ組(i<j<k)の問題
最小コスト
最大スコア
累積和テク:累積和や累積結果を前処理しておく
【問題集】累積和
最適化問題
NoviSteps1D
かなり悩んだ 問題へのリンク 問題概要 長さ の整数列 を 3 箇所で切って、4 つの連続する数列に切り分ける。このとき、4 つの区間の値の和を とするとき、 の最小値を求めよ。 制約 考えたこと こういうの、 連続する区間が 4 個だけであることを活かす解法…
グラフ
二部グラフ
DFS
BFS
DP
シーケンシャルDP
ARC-E
AtCoder
AtCoder700点
補グラフを考える
考察：補集合を考える
黄色diff
均等に分ける
そのまま覚えたいシンプル設定の中堅以上の典型問題
中堅以上の典型要素を詰め合わせた教育的問題
いわゆる本当に典型らしい典型ではあるけれども、「二部グラフ判定」と「ナップサック DP」とパートが 2 つあって重たい。 類題として AOJ 2370 RabbitWalking (二部グラフ判定からの部分和ナップサックが酷似) POJ 3692 Kindergarten (補グラフとって二部グ…
