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))を求めれば答えが求まる。