1604-C, *1300

Problem - C - Codeforces

문제

• 순열 $a_{1} a_{2}...a_{n}$ 가 주어질 때 다음과 같은 시행을 통해 순열이 모두 지워질 수 있는가?
• $(i+1)\nmid a_{i}$인 항은 지울 수 있다. 이 때 지운 후에는 바뀐 index 에 대해 이 시행을 적용한다

 

풀이

다음을 관찰하자

중간에 있는 항을 지우면 앞 항들은 erasability(지울 수 있음)가 유지되고 뒤 항들은 변한다
따라서 뒤 항부터 보면서 지우는게 중간이나 앞에서부터 지우는것보다 지울 수 있는 항을 유지하는 더 좋은 선택이다

다음과 같은 greedy 방식으로 푼다
1. 뒤에서부터 지울 수 있는건 지운다
2. 지우다가 막히면 앞에꺼 중 가장 가까이 있는 지울 수 있는 index를 찾아 지운다
   2-1 불가능 - 순열을 모두 지울 수 없다
   2-2 가능 - 다시 1로
※ 지울 수 있는 index 중 가장 가까이 있는것을 지우는 이유는 그 index 가 가장 뒤쪽에 위치하고 있기 때문이다. 즉, 지울 수 있는 항을 더 많이 유지할 수 있다.

 

풀이 2

노란색으로 표시된 $a_{4}$를 주목하여 보자
$a_{4}$는 index 1~4 사이에서만 지워진다
따라서 $a_{4}$가 2, 3, 4, 5로 모두 나누어 떨어진다면 $a_{4}$는 지울 수 없다

같은 이유로 임의의 항 $a_{i}$는 index 1~i 에서만 지워진다
또한 임의의 항 $a_{i}$에 대해 $a_{i}$가 2, 3, 4 ... (i+1)로 모두 나누어 떨어진다면 그 항은 지울 수 없다

Fact
$$j\mid a_{i},\text{for all}\ 2\leq j \leq i+1 \Leftrightarrow [2,\ 3,\ 4,\ ..., i+1]\mid a_{i}$$

Claim
임의의 $a_{i}$에 대해 $(j+1)\nmid a_{i}$인 $j(2\leq j \leq i+1)$가 존재하면 수열을 모두 지울 수 있다

∵
i) n = 1 일때