問題一覧 > 通常問題

No.2887 Minahoshi (Easy)

レベル : / AI推定難易度 : 500 / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / スペシャルジャッジ問題 (複数の解が存在する可能性があります)
タグ : (解説公開後に AC するまで非表示) / 解いたユーザー数 154
作問者 : 👑 seekworser / テスター : 👑 amentorimaru yuusaan
お気に入りにしたユーザー ProblemId : 11178 / 自分の提出
問題文最終更新日: 2024-09-12 11:12:54
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
yukicoder contest 446 (順位表) の他の問題:

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