この問題の解き方には色々な方針がありますが、そのうちの \(1\) つを紹介します。

まず、「綺麗さ」+「おいしさ」+「人気度」\(=X\) とし、 \(3\) 以上 \(3N\) 以下の各整数 \(k\) について、 \(X=k\) であるようなケーキがいくつあるかを求めます。
これは、 \(\{1,2, \dots , N\}\) から整数を \(1\) つ選ぶということを \(3\) 度繰り返し、選んだ整数の総和が \(k\) となる場合の数はいくつか、という問題の答えと一致します。
この問題は、dp[何回整数を選んだか][総和]={場合の数} という形の動的計画法で解くことができます。これを愚直に実装すると \(O(N^2)\) となってしまいますが、 \(dp[i][j]\) の遷移先が \(dp[i+1][j+1],dp[i+1][j+2], \dots dp[i+1][j+N]\) という区間になるので、累積和によって \(O(N)\) に高速化できます。

これにより、左から \(K\) 番目のケーキの \(X\) の値が分かりました。そこから先は、そのケーキの「綺麗さ」の値を仮定する \(O(N)\) のループによりこの問題を解くことができます。
具体的には、あるケーキの \(X\) の値と「綺麗さ」の値がわかれば、とりうる「おいしさ」の値はひとつの区間をなすので、その区間を「綺麗さ」ごとに求めていくようなループになります。詳しくは実装例も参照してください。

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

C++による実装例:

#include<bits/stdc++.h>

using namespace std;

int main(){
  int n;
  long long k;
  cin >> n >> k;
  long long dp[4][3000005]={0};
  dp[0][0]=1;
  for(int i=0;i<3;i++){
    for(int j=0;j<=i*n;j++){
      dp[i+1][j+1]+=dp[i][j];
      dp[i+1][j+n+1]-=dp[i][j];
    }
    for(int j=1;j<=(i+1)*n;j++){
      dp[i+1][j]+=dp[i+1][j-1];
    }
  }
  
  int x;
  for(int i=3;i<=3*n;i++){
    if(k<=dp[3][i]){x=i;break;}
    else{k-=dp[3][i];}
  }
  for(int i=1;i<=n;i++){
    int jmi=max(1,x-i-n);
    int jma=min(n,x-i-1);
    if(jmi>jma){continue;}
    if(k>(jma-jmi+1)){k-=(jma-jmi+1);continue;}
    int y=jmi+k-1;
    int z=x-i-y;
    cout << i << ' ' << y << ' ' << z << '\n';
    return 0;
  }
}

BONUS! この問題は、もう少し大きな制約でも解くことも、たくさんのケーキに対する問い合わせが来るような問題を解くこともできます。是非、いろいろな解法を検討してみてください。