No.2887 Minahoshi (Easy)
タグ : / 解いたユーザー数 154
作問者 : 👑
amentorimaru
Story
Minahoshi-chan is learning about strings.
While studying LCP arrays, she noticed that the string "mississippi" looks just like her own name "minahoshi", and she now wants to know more about LCP arrays.
For the sake of adorable Minahoshi-chan, let's solve a problem about LCP arrays.
Problem Statement
You are given a positive integer $N$. Construct a string of length $N$ consisting of a or b
such that the sum of the elements of its LCP array is maximized.
What is an LCP array?
For a string $S$ of length $N$, the array obtained by sorting the $N$ suffixes of $S$ in lexicographical order is called the suffix array of $S$.
The array obtained by computing, for $i = 1, 2, \dots, N-1$, the length of the longest common prefix of the $i$-th element and the $i+1$-th element of the suffix array of $S$ is called the LCP array (Longest Common Prefix Array) of $S$.
For example, the $4$ suffixes of $S =$ abba are
abba, bba, ba, a, and
sorting them in lexicographical order gives
[a, abba, ba, bba].
The lengths of the longest common prefixes of adjacent elements are $1$, $0$, $1$, so
the LCP array of the string abba is $[1, 0, 1]$.
Input
$N$
Constraints
- $2 \le N \le 2 \times 10^5$
- All inputs are integers.
Output
Output a string of length $N$ consisting of a or b
such that the sum of the elements of its LCP array is maximized.
If multiple strings satisfy the condition for the given $N$, any of them will be accepted.
Sample
Sample 1
Input
3
Output
aaa
The LCP array of aaa is $[ 1, 2 ]$, and its sum is $3$.
This is the maximum possible sum of an LCP array among strings of length $3$ consisting of a or b.
Other outputs such as bbb will also be judged AC.
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。