공식 해설만큼 선명하지는 않지만, 다른 방법으로도 그렇게 번거롭지 않고 풀 수 있었으므로, 그 해법을 메모합니다.

문제 문장 : AtCoder Grand Contest 023 C - Painting Machines

해법

다만 $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개 이하」라고 하는 생각은 아마 중요하므로, 이것을 원활하게 끌어낼 수 없었던 곳은 반성점입니다.