Divide by Zero 2021 and Codeforces Round #714 (Div. 2)

어려웠고 결과적으로 망했다. 역시 외부 연계 라운드는 무섭다. 민트로 똑떨함

 

A. Array and Peaks

일단 가능한 많은 peak이 존재하려면 peak 좌우에 더 작은 값들이 위치해야 한다. 그러면 한칸 걸러 한칸씩 peak이 등장하는 상태가 최대이고, 따라서 최대 floor( (N-1)/2 )개의 peak이 존재할 수 있다. 반대로 가장 적게 peak이 존재하는 경우는, 정렬된 상태면 하나도 없는 상태가 된다. 주어진 peak 갯수만큼, 최대로 만드는 전략으로 채운다. 빈 자리들에 오름차순으로 남은 수들을 채워 넣으면 된다.

 

B. AND Sequences

제일 극단적인 케이스를 생각해보면 a1 = a2 & ... & an 또는 a1 & ... & an-1 = an 일 것이다. 그런데 and 연산을 잘 생각해보면 비트가 꺼질 수는 있어도 켜질 수는 없다. 즉, a1 = a2 & ... & an 이면서 a1 & ... & an-1 = an를 만족하려면 a2 & ... an-1을 a1 또는 an과 and 연산 했을때, a1이나 an의 비트를 꺼서는 안된다. 따라서 a1 = an이 만족하고, a1 = an = a1 & ... & an-1 = a2 & ... & an 이다. a1 & ... & an-1 = a2 & ... & an 이면 a1 & ... & an = a1 & ... & an-1 = a2 & ... & an 이다.
여기까지 관찰을 하고, 구현을 하면 된다. a1 & ... & an을 구하고, 각 원소의 등장 횟수를 센다. a1과 an을 고정하고 a2~an-1에 잘 채워 넣는다고 생각해보면, a1과 an에 하나씩 원소를 배정해보면서 구할 수 있다. 어떤 원소가 2개 이상이면서 a1 & ... & an와 같으면 (즉, a1 = an = a1 & ... & an-1 = a2 & ... & an) 조건에 일치한다. 이 상태의 경우의 수는 (cnt)P(2) * (N-2)! 이다. 페르마 소정리 등을 사용해 경우의 수를 잘 계산하면 된다.

분명 B번인데 뭔가 잘못돼가고 있다는 느낌이 들었다... 체감은 한 C번인데 그냥 A번 풀지 말고 탈주할까 싶었다.

 

C. Add One (업솔빙)

각 숫자들이 변하는 형태는 독립적이므로, 따로 떼어놓고 생각해도 된다. 또한 어떤 숫자 'k'는 '0'이 k번 연산을 한 후와 동치이므로, 0으로 시작할 때의 규칙만 찾으면 된다. 완전탐색 코드를 짜보면 증가량이 이항계수 모양으로 나타난다... 까지 관찰을 하고 못풀었다.
Green55의 풀이는 다음과 같다. 여기서 '0'은 10번 연산을 하면 '1' 과 '0'으로 쪼개지니까 ('0'이 m초 지난 자릿수) = ('1'이 m-10초 지난 후 자릿수) + ('0'이 m-10초 지난 후 자릿수) 이다. ('1'이 m-10초 지난 후 자릿수) 는 위에서 말했다시피 ('0'이 m-9초 지난 후 자릿수) 이다. 그러면 ('0'이 m초 지난 자릿수) = ('0'이 m-9초 지난 후 자릿수) + ('0'이 m-10초 지난 후 자릿수). 이를 dp식으로 표현하면 dp[m] = dp[m-9] + dp[m-10]이다. 그에 더해, naive한 수열이 이항계수 비스무리한 형태면, 점화식이 선형일 확률이 매우 높으므로 벌래캠프로 해결할 수 있다.

대충 규칙이 있을거라곤 생각했지만, DP를 확실히 못하긴 한다. 연습 좀 더 해야겠다.