PS 이야기

비트 문자열이 있을 때, 각 자리의 비트를 switch 할 수 있는 규칙이 2가지 있다. 이 두 가지 규칙을 통하여 주어진 비트 문자열의 모든 자리를 0으로 만드는 최소 회수를 구하는 문제다. 문제를 뒤집어 모든 자리가 0으로 되어 있는 비트 문자열에서 입력으로 주어진 비트 문자열을 만들기 위한 최소 회수를 구하는 문제로 바꾸자. 그러면 이제 왼쪽에 있는 1비트 부터 차례대로 만드는 것이 회수를 최소화 한다. 아래와 같은 값을 미리 계산해둔다. D[i] = 비트문자열의 모든 자리가 0이라고 할 때, 오른쪽에서 i번째 비트를 1로 만드는 최소 회수 D[i] = D[i-1]*2+1, D[1] = 1 D[i] = 2^i - 1 가장 왼쪽에 있는 1비트를 만들기 위한 최소 회수는 몇 일까? 그 비트의 위치를 왼..

자동차가 C대 있고 각 자동차의 시작 위치가 다를 수 있다. 모든 자동차의 목적지는 1번 마을이고, 각 자동차는 최단 경로 중 임의의 한 경로로 이동한다고 하자. 두 자동차가 동시에 같은 마을에서 같은 도로를 이동할 수 없을 때, 목적지에 갈 수 있는 자동차의 최대 개수를 구하는 문제다. 이 문제는 2013년 월드 파이널 C번 문제와 지문 하나 다르지 않게 출제되었다. 다행히도 이 문제의 풀이를 미리 알고 푼 팀은 없는 것으로 알고 있다. 문제에서 제약 조건은 단 하나, 두 자동차가 동시에 같은 마을에서 같은 도로를 이동할 수 없다는 것이다. 두 자동차가 동시에 같은 마을에서 같은 도로를 이동하기 위한 필요충분조건은 두 자동차의 시작 마을에서 도착 마을로 가는 최단 거리가 같다는 조건이다. 따라서 자동차..

길이가 N인 문자열이 주어지고, 길이가 M인 패턴이 주어진다. 이 패턴의 연속된 일부분 혹은 전체를 한 번 뒤집어서 새로운 패턴들을 만들 수 있다. 길이가 N인 문자열에서 이렇게 만들어진 패턴들과 매치되는 부분 문자열이 몇 개인지 세어주는 문제다. N ≤ 1,000,000 이고 M ≤ 100 이다. 시간제한은 0.2초로 N에 선형인 시간복잡도를 요구한다. 길이가 M인 패턴에서 뒤집는 연산에 의해 만들어지는 새로운 패턴의 개수는 많아야 $M^2$개다. 즉, 이 문제는 길이가 M인 패턴 $M^2$개와 길이가 N인 문자열을 매칭하는 문제로 바꿀 수 있다. 이와 관련된 문제는 Aho-Corasick 자료구조를 이용하면된다. KMP와 같은 문자열 매칭 알고리즘은 하나의 패턴과 전체 문자열을 매칭하는 알고리즘인데,..