ここでは、OEISを用いた解法を紹介します。

便宜上、この解説では「綺麗さ」「おいしさ」「人気度」の値を本文中の値よりも \(1\) 低いものとして扱います。
すなわち、各パラメータは \(0\) 以上 \(N-1\) 以下の値をとるものとします。

まず、\(S\) を固定したとき、「綺麗さ」+「おいしさ」+「人気度」\(=S\) を満たすケーキの個数を \(f(N,S)\) とします。
また、\(T\) を固定したとき、「おいしさ」+「人気度」\(=T\) となるケーキの個数を \(g(N,T)\) とします。

ここで、\(f(N,S)\) と \(g(N,T)\) を十分高速に求めることができれば、この問題は十分高速に解くことができます。
具体的には、次の手順で解くことができます。

1. \(0≦k≦3N-3\) を満たす全ての \(k\) について、\(f(N,k)\) を求める
2. 1.の情報から「綺麗さ」+「おいしさ」+「人気度」の値 \(S\) を求める
3. \(0≦k≦N-1\) を満たす全ての \(k\) について、\(g(N,S-k)\) を求める
4. 3.の情報から「綺麗さ」の値 \(c\) を求める
5. 「おいしさ」+「人気度」\(=S-c\) を満たすケーキを全て調べ、適切なケーキを選ぶ

\(f(N,S)\) と \(g(N,T)\) を小さい値で実験します。

すると、例えば \(f(5,0),\dots f(5,12)\) は \(1, 3, 6,10,15,18,19,18,15,10, 6, 3, 1\) となり、これをそのままOEISで検索すると A109439 がヒットします。
これによって、

\[ f(N,S) = \begin{cases} (S+1)(S+2)/2 & (0≦S<N) \\ (9N-3N^2+6NS-6S-2S^2-4)/2 & (N≦S≦2N-3) \\ (3N-S-1)(3N-S-2)/2 & (2N-3<S≦3N-3) \\ \end{cases} \]

であることが分かります。

また、\(g(N, T)\) は実験から \(\min(T+1, 2N-1-T)\) となることが分かります。

よって、\(O(N)\) でこの問題を解くことができました。