레이팅 미적용*참고: 이 문제의 메모리 제한은 기본의 두 배인 512MB이다.*
수년간 대회를 열고 베시가 계속해서 1등을 차지하는 것을 지켜본 농부 존은 이것이 우연일 리 없다는 것을 깨달았다. 대신 그는 베시의 DNA에 승리가 새겨져 있음이 분명하다고 결론짓고, 이 "승리" 유전자를 찾아 나선다.
그는 이 "승리" 유전자의 후보를 식별하는 절차를 고안한다. 그는 베시의 게놈, 즉 길이 \(N\)(\(1 \leq N \leq 3000\))의 문자열 \(S\)를 가져온다. 그는 \(1 \leq L \leq K \leq N\)인 쌍 \((K,L)\)을 하나 골라, "승리" 유전자 후보가 길이 \(L\)이고 더 큰 길이 \(K\)의 부분 문자열 안에서 발견된다고 정한다. 유전자를 식별하기 위해, 그는 \(S\)의 모든 길이 \(K\) 부분 문자열(\(k\)-mer라고 부르자)을 가져온다. 각 \(k\)-mer에 대해, 그는 그 안의 모든 길이 \(L\) 부분 문자열을 살펴 사전순으로 가장 작은 부분 문자열을 승리 유전자 후보로 식별하고 (동률이면 가장 왼쪽에 있는 것을 선택), 그 부분 문자열이 \(S\)에서 시작하는 \(0\)-인덱스 위치 \(p_i\)를 집합 \(P\)에 기록한다.
아직 \(K\)와 \(L\)을 정하지 않았기 때문에, 그는 모든 쌍 \((K,L)\)에 대해 후보가 몇 개나 되는지 알고 싶다.
\(1\dots N\)의 각 \(v\)에 대해, \(|P|=v\)인 \((K,L)\) 쌍의 개수를 구하는 것을 도와주자.
문제 제공: Suhas Nagar
배점
- 입력 2-4: \(N \leq 100\)
- 입력 5-7: \(N \leq 500\)
- 입력 8-16: 추가 제약 없음.
문제 제공: Suhas Nagar
문자열의 길이를 나타내는 \(N\)과, 주어진 문자열 \(S\)가 주어진다. 소의 유전학은 인간의 것보다 훨씬 발전했으므로 모든 문자는 대문자(\(s_i \in A-Z\))임이 보장된다.
\(1\dots N\)의 각 \(v\)에 대해, \(|P|=v\)인 \((K,L)\) 쌍의 개수를 한 줄에 하나씩 출력한다.
8
AGTCAACG11
10
5
4
2
2
1
1In this test case, the third line of the output is 5 because we see that there are exactly 5 pairs of \(K\) and \(L\) that allow for
three "winning" gene candidates. These candidates are (where \(p_i\) is \(0\)-indexed):
(4,2) -> P = [0,3,4]
(5,3) -> P = [0,3,4]
(6,4) -> P = [0,3,4]
(6,5) -> P = [0,1,3]
(6,6) -> P = [0,1,2]
To see how (4,2) leads to these results, we take all \(4\)-mers
AGTC
GTCA
TCAA
CAAC
AACG
For each \(4\)-mer, we identify the lexicographically minimal length 2 substring
AGTC -> AG
GTCA -> CA
TCAA -> AA
CAAC -> AA
AACG -> AA
We take the positions of all these substrings in the original string and add
them to a set \(P\) to get \(P = [0,3,4]\).
On the other hand, if we focus on the pair \((4,1)\), we see that this only leads
to \(2\) total "winning" gene candidates. If we take all \(4\)-mers and identify the
lexicographically minimum length \(1\) substring (using A and A' and A* to
distinguish the different As), we get
AGTC -> A
GTCA' -> A'
TCA'A* -> A'
CA'A*C -> A'
A'A*CG -> A'
While both A' and A* are lexicographically minimal in the last 3 cases, the
leftmost substring takes precedence so A' is counted as the only candidate in
all of these cases. This means that \(P = [0,4]\).
riseoj 작성
출처 올림피아드 > USACO > 2023-2024 > US Open > Silver