냐 공통 부분 수열 확장 문제 링크 서브태스크 구성도 좋고, 재미있게 풀었다. 풀이 및 코드 Subtask #1: $|W|=1$(14점) 더보기 자명하다. 왼쪽 확장 경우, 오른쪽 확장 경우로 나눠서 각각 쌍이 존재하는지 확인하면 된다. 하지만 Subtask #2도 충분히 쉬우므로 한번에 긁었다. Subtask #2: $\sum |X|, \sum |Y| \le 300$(17점) 더보기 $W$의 모든 위치에 대해서 문자 $c$를 끼워 넣은 경우에도 여전히 $|X|$와 $|Y|$의 부분 수열이 되는가를 판단하면 된다. 그러면 $\mathcal O(|W|\times |C|\times (|X|+|Y|+|W|))$의 시간이 걸린다. 따라서 대충 $26\times 300^2\approx 2\cdot 10^6$번의 ..