コンテストでの時間切れや解けなかった過去問を振り返って供養していく
問題
Difficulty: 1955 (記事作成時点)
供養
解法
- おいしさと人気度の合計を $S^{'}$ としたとき、おいしさを $1 \le y \le N$ に決め打てば人気度も一意に定まり、それらのパターン数 $F(S^{'})$ は $F(S^{'}) = \mathrm{max}(\mathrm{min}(S^{'} - 1, 2N + 1 - S^{'}), 0)$ となる
- 3つのパラメータの合計を $S$ とすると、綺麗さを $x$ に決め打てば残り2つの合計値が決まるので、パターン数 $G(S)$ は $G(S) = \sum_{x = 1}^{N}F(S - x)$ となる
- $G(S) = G(S - 1) + F(S - 1) - F(S - N - 1)$ と順に求めることができる
- 上記より、$\sum_{i = 3}^{S - 1} G(i) \lt K \le \sum_{i = 3}^{S} G(i)$ であるような $S$ を求めることができる
- $S$ が固定されたので、$\sum_{j = 1}^{x - 1} F(S - j) \lt K - \sum_{i = 3}^{S - 1} G(i) \le \sum_{j = 1}^{x} F(S - j)$ であるような $x$ を求めることができる
- $S, x$ が固定されたので、$k = K - \sum_{i = 3}^{S - 1} G(i) - \sum_{j = 1}^{x - 1} F(S - j)$ としたときに $y = k + \mathrm{max}(S - x - N - 1, 0), z = S - x - y$ と求めることができる
- $(x, y, z)$ を出力する
実装
計算量は $O(N)$
公式解説
躓いた点
