区分線形最適化ページの位置づけ
| 項目 | 内容 |
|---|---|
| 必修度 | 発展 |
| 学習目安 | 発展 |
| 前提 | 座標・二分探索 |
| 対象問題 | 4問（推定値あり4問、未算出0問） |
この記事のdifficulty区分は、問題を解く順番を決めるための目安です。AtCoderの公式なA〜F区分ではなく、取得できたdifficulty推定値を次の範囲に分けています。
| 学習目安 | difficulty推定値 | 問題数 |
|---|---|---|
| 入門 | difficulty < 0 | 1 |
| 標準 | 0〜799 | 1 |
| 標準〜発展 | 800〜1199 | 0 |
| 発展 | 1200以上 | 2 |
| 未算出 | — | 0 |
最大・最小の担当点が切り替わる時刻だけを候補にし、区分線形な面積や値を評価します。
問題ごとの細かな実装は異なりますが、最初に確認する条件は共通しています。
区分線形最適化の見分け方
- 時間に対して座標が直線的に変化する
- 最大・最小の担当が有限の時刻で切り替わる
- 全時刻を連続的に調べる必要がある
区分線形最適化の実装前チェック
- 切替時刻を全て列挙する
- 候補時刻の前後で担当点を確認する
- 浮動小数点の誤差と区間端点を検算する
先に確認する文法・ライブラリ
まずは必須Python文法で、入力・配列・条件分岐・ループなどの基本を確認してください。問題に合わせたキュー、ヒープ、二分探索などの選び方は標準ライブラリ・定石にまとめています。
代表問題で実装を確認する
最初の一問として、ABC159 C Maximum Volume（公式解説）を解きます。3辺の合計がLなら、体積は3辺が等しいとき最大になります。Lを3等分して立方体の体積を計算します。
L = int(input())
print((L / 3) ** 3)式を1回計算するO(1)時間・O(1)メモリです。
区分線形最適化の学ぶ順番
このページでは全件を一度に並べず、difficultyの推定値を目安に代表問題を段階分けしています。難易度が未算出の問題は、制約と出題意図を先に確認します。
まず解く
| 問題 | 公式解説 | 出題意図 | difficulty |
|---|---|---|---|
| ABC159 C Maximum Volume | 公式解説 | 和がLに固定された直方体の体積は相加相乗平均より3辺が等しいとき最大で、(L/3)^3となる。 | -104 |
| ABC165 D Floor Function | 公式解説 | 関数のB周期性でxを0以上B未満に縮約し、単調性からx=min(B−1,N)だけを評価する。 | 600 |
| ABC196 E Filters | 公式解説 | Track the image of an interval under repeated add/subtract/clamp operations and evaluate each query by clamping its value. | 1650 |
| ABC130 F Minimum Bounding Box | 公式解説 | 各軸の最大・最小座標が切り替わる時刻で区分線形に分け、候補時刻の面積を評価する。 | 2240 |
問題文を読んだら、まず「見分け方」のどれに当たるかを一行で記録します。当てはまらない問題は、別のページへ移す判断自体を復習材料にします。
