No.2887 Minahoshi (Easy)
タグ : / 解いたユーザー数 136
作問者 : 👑
seekworser
/ テスター :
👑 
amentorimaru
yuusaan
ストーリー
みなほしちゃんは文字列について学んでいます。
LCP array について勉強したとき、"mississippi" という文字列は 自分の名前 "minahoshi" にそっくりなことに気が付き、 LCP array についてもっと詳しく知りたくなりました。
かわいいみなほしちゃんのために LCP array についての問題を解いてあげましょう。
問題文
正整数 $N$ が与えられます。a または b からなる長さ $N$ の文字列であって
LCP array の要素の総和が最大となるものを構築してください。
LCP array とは
長さ $N$ の文字列 $S$ について、$S$ の $N$ 個の suffix （接尾辞）を辞書順でソートした配列を $S$ の suffix array と言います。
$i = 1, 2, \dots, N-1$ について、$S$ の suffix array の $i$ 番目の要素と $i+1$ 番目の要素の最長共通接頭辞の長さを求めた配列を $S$ の LCP array (Longest Common Prefix Array) と言います。
例えば、$S =$ abba の $4$ つの接尾辞は
abba, bba, ba, a で、
これらを辞書順にソートすると
[a, abba, ba, bba] となります。
隣接要素同士の最長共通接頭辞の長さは $1$, $0$, $1$ なので、
文字列 abba の LCP array は $[1, 0, 1]$ となります。
入力
$N$
制約
- $2 \le N \le 2 \times 10^5$
- 入力はすべて整数
出力
a または b からなる長さ $N$ の文字列であって
LCP array の要素の総和が最大となる文字列を出力せよ。
与えられた $N$ に対して複数の文字列が条件を満たす場合、 いずれを出力しても正解とみなされる。
サンプル
サンプル1
入力
3
出力
aaa
aaa の LCP array は $[ 1, 2 ]$であり、総和は $3$ です。
これは、長さ $3$ の a または b からなる文字列として考えられる LCP array の総和として最大の値となります。
この他、 bbb などを出力しても AC となります。
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。