AGC023-C Painting Machines

問題概要

・N個のますとN-1個のペイントマシーンがある。

・最初、ますはすべて白

・ペイントマシーンiはiとi+1のますを黒にする。

・ペイントマシーンを順列Pの順番で稼働させる

・すべてのますが初めて黒になったとき、ペイントマシンがK回稼働していたらその順列のスコアはKとなる。

・すべての順列でのスコアの総和を求める。

解法の概要

マシンをK回動かしたときにすべてのますが黒になっている順列の数をf(K)とする。

スコアがちょうどKとなる順列はf(K) - f(K-1)個ある。したがってΣ[K = 1...N-1]K*(f(K)-f(K-1))が答えとなる。

解法

f(K)を求める。最初のK回に動かすマシンをA型、そうでないものをB型とする。(B型のマシンは必ずすべてのますが黒に塗られた後に稼働する)それぞれのマシンをA型かB型かを決める通り数をg(K)とする。

ここで、B型のマシンの両隣は必ずA型のマシンになることに注意する。したがってA型のマシンとA型のマシンの間にあるB型のマシンは最大で1つである。

g(K)は(K-1)個あるA型のマシンとA型のマシンの中から(N-1-K)個選んでB型のマシンを配置する組み合わせなのでg(K) = C(K-1,N-1-K)がなりたつ。(Cは二項係数)

A型のマシンの順列はK!、B型のマシンの順列は(N-1-K)!なのでf(K) = C(K-1,N-1-K) * K! * (N-1-K)!となる。

あとはf(1),f(2),...f(N-1)を求め、それを利用してΣ[K = 1...N-1]K*(f(K)-f(K-1))を求めれば答えが求まる。