CodeTON Round 3 (Div. 1 + Div. 2)

A. Indirect Sort (0:01, +)

\(A_1\)이 1이어야 한다.

 

B. Maximum Substring (0:05, +)

어떤 부분문자열에 두 문자가 하나 이상 있으면 그냥 쭉 늘려주는 것이 최적이다. 따라서 전체 문자열의 값과 같은 문자가 연속으로 가장 길게 있는 경우만 비교해주면 된다.

 

C. Complementary XOR (0:20, +)

모든 숫자가 0인 경우부터 거꾸로 생각해보자. 이 상태에서 연산을 한 번 적용하면 A와 B의 모든 원소가 다른 값이 되고, 한번 더 적용하면 다시 A와 B의 모든 원소가 같아진다. 따라서 가능한 경우는 A와 B가 모두 같거나 모두 다른 경우이다. 해를 찾는 방법은 A를 우선 모두 1로 만들자. 이러면 B가 모두 0이거나 모두 1인데, 모두 0이면 1 N, 모두 1이면 1 1 / 2 N을 써 주면 된다.

 

D. Count GCD (0:47, +1)

자명하게, \(A_i\)는 \(A_{i+1}\)의 배수여야 한다. \(m \leq 10^9\)이므로 \(A_i\)의 값은 대략 30번 변한다. \(A_i\)가 같은 값끼리 묶어 생각해주면, 각 수는 \(kA_i\)꼴이 될 수 있는데 첫 수에 대한 \(k\)는 \(\frac{A_i}{A_{i+1}}\)과 서로소여야 하며, 두 번째 수 부터는 \(k\)가 어떤 값이어도 된다. 따라서, \(x\) 이하의 수 중 \(y\)와 서로소인 수의 개수를 구하는 것을 대략 30번 하면 되는데, 이는 소인수분해 후 포함배제로 해결할 수 있다. 서로 다른 소인수의 개수가 많아야 10개이기 때문에 많아도 \(30 \times (\sqrt{10^9} + 2^{10})\)정도의 연산량으로 해결할 수 있다.

 

이후 거의 2시간 동안 E를 보았지만 풀지 못했다. E를 풀지 못했지만 D까지 페널티 관리를 잘 한 덕에 + Div. 1+2라서 레이팅이 올라 개인 최고 레이팅을 찍을 수 있었다.