We show that by working in a basis similar to that of the natural transition orbitals and using a modified zeroth order Hamiltonian, the cost of a recently-introduced perturbative correction to excited state mean field theory can be reduced from seventh to fifth order in the system size. The (occupied)$^2$(virtual)$^3$ asymptotic scaling matches that of ground state second order M{o}ller-Plesset theory, but with a significantly higher prefactor because the bottleneck is iterative: it appears in the Krylov-subspace-based solution of the linear equation that yields the first order wave function. Here we discuss the details of the modified zeroth order Hamiltonian we use to reduce the cost as well as the automatic code generation process we used to derive and verify the cost scaling of the different terms. Overall, we find that our modifications have little impact on the methods accuracy, which remains competitive with singles and doubles equation-of-motion coupled cluster.