| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 1 초 | 1024 MB | 38 | 16 | 14 | 53.846% |
After years of hosting games and watching Bessie get first place over and over, Farmer John has realized that this can't be accidental. Instead, he concludes that Bessie must have winning coded into her DNA so he sets out to find this "winning" gene.
He devises a process to identify possible candidates for this "winning" gene. He takes Bessie's genome, which is a string $S$ of length $N$ where 1ドル \leq N \leq 3000$. He picks some pair $(K,L)$ where 1ドル \leq L \leq K \leq N$ representing that the "winning" gene candidates will have length $L$ and will be found within a larger $K$ length substring. To identify the gene, he takes all $K$ length substrings from $S$ which we will call a $k$-mer. For a given $k$-mer, he takes all length $L$ substrings, identifies the lexicographically minimal substring as a winning gene candidate (choosing the leftmost such substring if there is a tie), and then writes down the 0ドル$-indexed position $p_i$ where that substring starts in $S$ to a set $P$.
Since he hasn't picked $K$ and $L$ yet, he wants to know how many candidates there will be for every pair of $(K,L)$.
For each $v$ in 1ドル\dots N,ドル help him determine the number of $(K,L)$ pairs with $|P|=v$.
$N$ representing the length of the string. $S$ representing the given string. All characters are guaranteed to be uppercase characters where $s_i \in A-Z$ since bovine genetics are far more advanced than ours.
8 AGTCAACG
11 10 5 4 2 2 1 1
In 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]$.