解法

ちょうど$K$個稼働したときに全部塗れるような順列の個数$g(K)$を数えられれば、答はそれにスコア$K$を重みづけ和することで求まる。

\prod_K K*g(K)

以下では$g(K)$をいかに求めるかを考える。

全部塗れたときの稼働マシンと未稼働マシンの並び方を考えると、未稼働マシンは、

端にない
連続しない

という2つの条件を満たした状態になっている。しかし、逆に2条件を満たしても、ちょうど$K$個稼働したときに全部塗り終わったとは限らない。$K$個目を稼働する前に全部塗れていることがある。ここで公式解説では（$K$のときの値）－（$K-1$のときの値）とすることでちょうど$K$個のときの値である$g(K)$を求めているが、自分は思いつかなかった。

自分が考えたのは、直前である$K-1$個稼働時の状態。その時点では全部塗れておらず、次の1つを稼働すると全部塗れる状態である。これは以下の3通りである：

(1) 端1つ未稼働: 左右端のマシンはどちらか一方だけ未稼働。端以外のマシンで、未稼働なものが連続することはない、という状態。次に端のマシンを稼働すれば全部塗れる。
(2) 2連続未稼働: 左右端のマシンは両方稼働。未稼働マシンのうち2つが連続し、他は連続しない、という状態。次に2連続未稼働マシンのどちらかを稼働すれば全部塗れる。
(3) 3連続未稼働: (2)と同様で、未稼働マシンが2連続ではなく3連続のもの。次に3連続の中央のマシンを稼働すれば全部塗れる。

後は、上記(1)～(3)に該当する順列の個数（それぞれ$g_1(K),$ $g_2(K),$ $g_3(K)$とする）を数えればよい。$g_1(K)$～$g_3(K)$は以下の通り計算できる。以下、$K-1$個稼働時の未稼働マシンの数を$r=N-K$と置く。

g_1(K) = 2 *  {}_{K-1}C_{r-1} * (K-1)! * 1 * (r-1)!

式	意味
$2$	左右どちらの端が未稼働か
${}_{K-1}C_{r-1}$	稼働マシンの隙間に未稼働マシンを挿入する組合せ
$(K-1)!$	稼働マシン$K-1$個の稼働順序
$1$	$K$番目に稼働するのは端のマシン一択
$(r-1)!$	残りの未稼働マシンの稼働順序

g_2(K) = {}_{K-2}C_{r-1} * (r-1) * (K-1)! * 2 * (r-1)!

式	意味
${}_{K-2}C_{r-1}$	稼働マシンの隙間に未稼働マシンを挿入する組合せ（連続する2つはまとめて1つと考える）
$r-1$	未稼働マシンを2つ入れる場所の選択
$(K-1)!$	稼働マシン$K-1$個の稼働順序
$2$	$K$番目に稼働するのは2連続の未稼働マシンのどちらか
$(r-1)!$	残りの未稼働マシンの稼働順序

g_3(K) = {}_{K-2}C_{r-2} * (r-2) * (K-1)! * 1 * (r-1)!

式	意味
${}_{K-2}C_{r-2}$	稼働マシンの隙間に未稼働マシンを挿入する組合せ（連続する3つはまとめて1つと考える）
$r-2$	未稼働マシンを3つ入れる場所の選択
$(K-1)!$	稼働マシン$K-1$個の稼働順序
$1$	$K$番目に稼働するのは3連続の中央のマシン一択
$(r-1)!$	残りの未稼働マシンの稼働順序

以上より、$g(K)=g_1(K)+g_2(K)+g_3(K)$で$g(K)$が求まり、答が求まる。

感想

場合分けの「3連続未稼働」に気づかず、かなりはまってしまいました。それでも体感的には他の橙diffより易しく感じました。
公式解説の「ちょうどK個＝K個以下-K-1個以下」という考え方はおそらく重要なので、これをスムーズに引き出せなかったところは反省点です。

解法メモ AtCoder Grand Contest 023 C - Painting Machines

解法

感想