問題一覧 > 通常問題

No.3001 Snake String

レベル : / AI推定難易度 : 1525 / 実行時間制限 : 1ケース 1.500秒 / メモリ制限 : 512 MB / スペシャルジャッジ問題 (複数の解が存在する可能性があります)
タグ : (AC するまで非表示) / 解いたユーザー数 20
作問者 : addeight2 / テスター : 👑 p-adic
お気に入りにしたユーザー ProblemId : 11721 / 自分の提出
問題文最終更新日: 2024-12-31 19:32:11
This statement was translated by AI (claude-opus-5-5, effort medium) and may contain errors or differ in nuance from the original. The original statement takes precedence. Back to the original

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もしくは右上の雲マークをクリックしてアカウントを作成してください。