수열 연산

각 수열을 $X_i=2\sum_{k<i}A_k+A_i$로 변환한다. 위치 $i$를 삭제했을 때, 뒤쪽 위치 $j$까지의 거리가 홀수이면 앞부분 합은 $A_i$만큼 감소하고 원소는 $2A_i$만큼 증가한다. 거리가 짝수이면 앞부분 합은 $A_i$만큼 증가하고 원소는 $2A_i$만큼 감소한다. 따라서 변환한 값은 바뀌지 않고 해당 위치만 삭제된다. 변환은 가역적이다. 앞부분 합 $P$를 알고 있으면 다음 원소는 $X_i-2P$이다. 그러므로 두 수열을 같게 만드는 것은 변환한 두 수열의 공통 부분수열을 남기는 것과 같다. LCS 길이를 $L$이라 하면 답은 $N+M-2L$이다. 서브태스크 1은 모든 삭제 상태를 실제 연산으로 열거하고 공통 상태를 비교한다. 상태는 최대 $2^N$개이며, 정렬 집합을 이용한 보수적 시간 상계는 $O((2^N+2^M)(N+M)^3)$이다. 전체 풀이는 LCS DP를 사용하며 시간 $O(NM)$, 메모리 $O(M)$이다. 원래 변환값 절댓값은 $49\,995\,000$ 이하이다. 삭제 후에도 이 값의 부분수열이므로 복원된 모든 원소 절댓값은 $(2\cdot5000-1)49\,995\,000<5\cdot10^{11}$이다. 64비트 정수로 충분하다. Solution written by GPT6.1