OMCE011

https://onlinemathcontest.com/contests/omce011/tasks/3773

수열 $a_1, a_2 \dots , a_n$​는 각 원소가 $1$이상 $3$이하의 정수로 이루어져 있으며, 아래와 같은 조건을 만족한다고 합니다:

1. $a_{n+1}=a_1, a_{n+2}=a_2$​로 정의되어, 수열은 순환합니다.
2. $n$ 이하의 모든 양의 정수 $k$에 대해 $a_{k}\neq a_{k+1}$​가 성립합니다.
3. $n$ 이하의 양의 정수 $i$ 중에서, 아래의 조건을 만족하는 경우의 수가 각각 주어집니다:
   • $ (a_i,a_{i+1})=(1, 3) $ 인 경우: $132$개
   • $ (a_i,a_{i+1})=(2, 1) $ 인 경우: $213$개
   • $ (a_i,a_{i+1})=(3, 2) $ 인 경우: $321$개
   • $ (a_i ,a_{i+1} ,a_{i+2})=(1, 2, 3) $ 인 경우: $123$개

이러한 조건을 만족하는 수열이 존재하는 모든 가능한 $n$의 값의 합을 구하시오.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

풀이 숨기는 법을 잘 몰라서 아래로 그냥 내렸습니다.

 

잘 생각해보면 이는 오일러 회로 문제로 환원할 수 있습니다.

정점 $1$, $2$, $3$이 있고, $a_i$에서 $a_{i+1}$로 가는 간선이 있다고 생각합시다. 이는 분명히 오일러 회로를 이룹니다.

간선의 총 용량 합이 $N$이고,

• $2 \to 1$의 횟수가 $213$회
• $3 \to 2$의 횟수가 $321$회
• $1 \to 3$의 횟수가 $132$회
• $1 \to 2 \to 3$의 횟수가 $123$회

인 오일러 회로가 존재하는지 묻는 문제와 같습니다.

 

• $2 \to 1$의 횟수가 $213$회

와 같은 조건은 간단하게 $2 \to 1$ 의 간선 용량이 $213$인 것으로 환원할 수 있습니다. 하지만

• $1 \to 2 \to 3$의 횟수가 $123$회

이 조건은 하나의 간선으로는 표현하기 힘듭니다. 여기서 정점 분할을 해 봅시다.

$2$정점을 $2up$과 $2down$ 2개로 분할해봅시다.

 

위와 같이 모델링하면, $2up -> 3$의 용량이 $123$인 것으로 환원할 수 있습니다. 

유향 그래프에서 오일러 회로가 존재할 필요충분조건은 $입차수 = 출차수$이므로, 남은 모든 간선에 $a, b, c .. e$와 같이 변수를 두고 식계산을 하면 일변수에 대한 식으로 모든 용량이 표현됩니다. 그 후 $$간선용량\geq  0$$을 적용하면 원하는 결과를 얻습니다.