1591: 수열 복원

문제 링크

일단, 이웃한 \((M+1)\)개의 숫자들에 대해서, 앞의 \(M\)개와 뒤의 \(M\)개는 \((M-1)\)개가 겹친다.
그렇다면, \((N-M+1)\)개의 수열에서, 한 수열에서 \((M-1)\)개가 겹치는 다른 수열로 옮겨간다고 생각할 수 있다.
그런데 \((N-M+1)\)개를 정점으로 잡으면 Hamiltonian Path를 구해야 하기 때문에 복잡하다.
따라서, \((M-1)\)개를 정점으로 잡고, 각각의 \((N-M+1)\)개의 수열을 간선으로 만들면 Euler Tour를 구하면 된다.
(M-1)개를 효과적으로 관리하기 위하여 나는 해싱을 사용했다.