No.3001 Snake String
Problem Statement
We define a string $T$ to be a "snake string" as follows.
Let $N$ be the length of $T$. There exists an integer $i\ (1 \le i \le N - 1)$ such that splitting $T$ between the $i$-th and $i + 1$-th characters and swapping the first and second parts gives back the original string $T$.
That is, $T = T_{i + 1} T_{i + 2} ... T_N T_1 T_2 ... T_i$ holds. ($T_i$ denotes the $i$-th character of $T$.)
You are given a string $S$ consisting of uppercase English letters. Let $N$ be the length of $S$. You may repeat the following operation any number of times.
Choose an integer $i\ (1 \le i \le N)$ and replace $S_i$ with any uppercase English letter of your choice.
Turn $S$ into a snake string $S^\prime$ using as few operations as possible.
Input
$S$
$S$ is a string consisting of uppercase English letters.
The length $|S|$ of $S$ satisfies $2 \le |S| \le 2 \times 10^6$.
Output
$S^\prime$
If there are multiple possible answers $S^\prime$, you may output any of them.
Print a newline at the end.
Notes
- If your submitted program gets TLE (Time Limit Exceeded), consider whether your algorithm can be made more efficient.
- Depending on the language used, you may get TLE even if your algorithm is correct. If you use Python, we recommend using PyPy, a faster implementation, rather than the standard Python implementation (CPython). It has been confirmed that C++ and PyPy can finish within the time limit.
Sample
Sample 1
Input
ABCBBBACC
Output
ABCABCABC
Replacing the 4th, 6th, and 8th characters with A, C, and B respectively gives ABCABCABC, which is a snake string. (Split it between the 3rd and 4th characters.) It is impossible to make a snake string with fewer than 3 character replacements, so ABCABCABC is an answer.
Sample 2
Input
ABCDEFG
Output
AAAAAAA
Replacing the 2nd through 7th characters with A gives AAAAAAA, which is a snake string. (Split it between the 1st and 2nd characters.) ABCDEFG cannot be turned into a snake string with fewer than 6 character replacements, so AAAAAAA is a correct answer. (Note that BBBBBBB and others are also correct answers.)
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。
addeight2