https://www.acmicpc.net/problem/24730
문제요약
- 수열을 GGG<>로 나타냄
- 단일항
- 초항, 공차
- 초항, 계차수열 : 계차수열은 수열의 값들의 차이(=계차)들의 수열임 => 초항을 두고 계차수열을 수열로 생각하고 GGG를 표현해라 => 재귀적인 느낌
- 수열은 f(x) = N차 다항식 의 f(0), f(1), ... 으로 구성되어있음
- GGG를 짧게할 수 있으면 짧게 해라 => Fake 조건
- N은 4천, 최고차항은 0이 아님
- 문제를 바로 이해하기는 참 어렵지만 재귀 비슷한 것이 나타나고 차이가 수열을 이루는데 차이의 차이가 수열을 이루고,.... 이런 생각은 해볼 수 있음
접근법
- 미분 같은걸 해야하나 고민했는데 잘 안됨
- 계차수열은 어떻게 생겼나...보기 위해 f(x + 1) - f(x)를 구해봄
- 최고차항이 빠지고
- 같은 차수끼리 모아지고 하면서 규칙이 보일 것 같은데 잘 안보임
- 3차, 4차까지는 되는데....
- n차 다항식은 조합(nCr)으로 계수는 구하겠음
- 계수를 구하면 f(x + 1) - f(x)는 구하겠는데, 한번 구할때 각 항마다 n번씩 총 n번을 수행해야하는데 이 것을 n번 반복해야함....
- 일단 f(0), f(1), f(2), .... 값을 구해봄
- 값 구하는 것은 쉬울 줄 알았는데 나중에 발목잡힘
- pow의 분할정복 기법을 이용해서 구해봄 => 시간초과의 원인
- 일단 이 상태에서 f(0)이 초항이 되는 것은 알겠고 이제 할 일은 계차에 대해서 뭔가 구하는 것임. 즉 G(f(0), G(계차에 대해서 작업))
- 그럼 일단 첫번째 계차를 구해봄 => 항끼리 빼면 구함
- f(1) - f(0), f(2) - f(1), ....
- 편의상 f'(0), f'(1), f'(2), .... 로 표현해보겠음
- 그럼 여기서 일단 가장 앞에 있는 것이 초항인지는 알겠음 : f'(0) = f(1) - f(0)
- 즉 G(f'(0), G(계차 수열))
- 그럼 두번째 계차를 구해봄
- f'(1) - f'(0), f'(2) - f'(1), ....
- 앞에 했던 것이랑 비슷함. 일단 초항을 구하고, 계차수열을 구해서 작업하고...
- 이게 진짜 되나??? 예제에 대해서 해보고, 임의로 간단한 다항식(4차정도)를 만들어서 해봄 => 진짜 됨
- 정리하면
- 수열을 만듬 => 0번째 것 얻음
- 수열끼리 빼서 계차 수열을 만듬 => 0번째 것 얻음
- 또 계차 수열을 만듬 => 0번째 것 얻음
- 반복
주의점
- 부분점수 문제라 부분문제의 실패시 왜 실패인지 모름
- 답이 틀렸나
- 시간초과인가
- 다른 뭔가가 있나
- 수열을 줄인답시고 중간에 0이나 같은게 나오면 처리를 하는 로직을 넣어볼 수도 있는데, MOD 연산으로 인해 실제로 값이 있지만 0이 나올수도 있고, 실제로 다르지만 같다고 판단할 수도 있고 여러모로 적절하지 못함
- 거듭제곱
- 거듭제곱을 구할때 분할정복으로 해서 logN = log4000 = 12 의 연산시간을 써서 f(x)를 구했고
- NlogN + N^N / 2의 연산을 했는데 4000이상의 테스트케이스에서 시간초과가 발생하는 것 같음
- f(x)의 특성상 0차부터 N차까지 연산을 하니까 굳이 위와같이 안하고 x를 하나씩 곱해가는 방식으로 변경해봤고, 이 경우에는 N + N^N/2의 연산을 수행하는데 이 경우는 통과함
- 모르겠음. 그 와중에 pypy3는 시간초과가 계속 발생해서 포기함
newbieski