AtCoder Grand Contest 066

https://atcoder.jp/contests/agc066/tasks

 

아... 이건 좀

A가 2086, B가 2162, C는 3036

게다가 E는 USACO에 같은 문제 + 중국인들 공유 이슈로 꽤나 풀리게 되었다.

아무튼 A 밖에 못 풀고 조졌다.

 

A. Adjacent Difference

 

거의 보자마자 생각보다 나쁘지 않은 발상을 만들었었다.

체스판 느낌으로 홀수칸에는 X 이하의 숫자가 오도록, 그리고 짝수칸에는 X + d 이상의 숫자가 오게 하는 것이다.

당연히 역으로 짝수칸에 X + d 이상이 오게, 홀수칸에 X 이하가 오도록 하는 것도 고려해보아야 한다.

그러나 이 발상을 발전시키지 못해서 잠시 삽질을 했다.

무슨 삽질을 했냐면, 적당히 (0, 0)부터 순서대로 숫자들을 잘 결정해 나가면 될 것이라는 생각이었다.

 

아무튼 다시 체스판으로 돌아와서.

이번에는 홀수칸에는 2kd + X가 오고 짝수칸에는 2kd + (X + d) % (2d)가 오도록 하는 것이다.

대충 몇 번 돌려본 결과 항상 1/2d * N^2 이하가 되도록 하는 경우가 존재한다!

O(N^2 * (2d))가 조금 걱정되어서 5분 정도 고민하다가 그냥 증명 없이 제출하였다.

 

업솔빙 느낌으로 증명을 좀 해보자...

모든 숫자에 대해서 제일 가까운 (2k) * d까지의 거리와 (2k + 1) * d까지의 거리는 반드시 d이다.

그러면 모든 칸에 대해서 제일 가까운 (2k) * d까지의 거리와 (2k + 1) * d까지의 거리는 정확히 N^2d이다.

따라서 그러면 X = 0인 경우와 X = d인 경우에 대해 모든 거리(= 비용)의 합이 정확히 N^2d라는 뜻이다.

따라서 둘 중 하나는 1/2d * N^2 이하.

 

B. Decreasing Digit Sums

 

Jiangly의 제출을 보고 적잖은 충격을 먹었다

사실 에디토리얼이 대충 무슨말 하는지는 알겠는데 마음에 드는 결론은 아니다.

5^i 아니면 (5^i) * j가 관찰해보면 적당히 2배씩해도 적당히 작아진다.

직관상으로 설명해야 하는데, 5^i은 2배했을 때 결국 5^(i - 1) * 10이니 자릿수의 합이 5^(i - 1)과 같다.

일반적으로는 숫자가 5배 작아지면 자릿수의 합이 작아질테니, 적당히 작아짐을 알 수 있다.

따라서 이들을 적당히 믹스하면(concatenate하면) 전체적으로 작아지는게 합쳐지면서 계속 작아진다.

 

또다른 방법을 찾았는데 내가 구현한 코드를 참고하라

10^p - x라는 숫자를 생각해보자.

\(2^k\,*(10^p-x) = (2^k-1)*10^p + (10^p - 1) - (2^k*x - 1)\) 와 같이 식정리를 할 수 있다.

이때 10^p - 1은 9가 p개 연속해 있는 것이므로 2^k * x - 1을 뺄 때 자리내림 등이 전혀 발생하지 않는다.

\(f(2^k\,*(10^p-x)) = f(2^k-1) + 9p - f(2^k*x - 1)\) 가 가능하다는 뜻이다!

아까와 비슷한 논리로 f(2^k - 1)보다는 f(2^k * x - 1)이 더 빨리 커지므로 k가 커질 수록 적당히 감소한다.

따라서 10^p - x의 여러 x를 대입하여 concatenate하면 된다.