問題一覧 > 通常問題

No.2893 Minahoshi (Hard)

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / スペシャルジャッジ問題 （複数の解が存在する可能性があります）
タグ : / 解いたユーザー数 8
作問者 : 👑 seekworserseekworser / テスター : 👑 amentorimaruamentorimaru kemunikukemuniku
1 ProblemId : 11140 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2024-09-12 11:10:07

ストーリー

みなほし「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) と言います。

この問題はマルチテストケースです。$T$ 個のテストケースについて回答してください。

入力

$T$
$case_1$
$\vdots$
$case_T$

$i = 1, 2, \dots, T$ について、$case_i$ は以下の形式で与えられる。 

$N$

制約

  • $1 \le T \le 600$
  • $2 \le N \le 2 \times 10^5$
  • すべてのテストケースについての $N$ の総和は $2 \times 10^5$ 以下である。
  • 入力はすべて整数

出力

$T$ 行出力せよ。$i$ 行目には $i$ 番目のテストケースについて、 a または b からなる長さ $N$ の文字列であって LCP array の要素の総和が最小となる文字列を出力せよ。

与えられた $N$ に対して複数の文字列が条件を満たす場合、 いずれを出力しても正解とみなされる。

サンプル

サンプル1
入力
3
2
3
4
出力
ab
abb
aabb

ab の LCP array は $[ 0 ]$であり、総和は $0$ です。

abb の LCP array は $[ 0,\ 1 ]$であり、総和は $1$ です。

aabb の LCP array は $[ 1,\ 0,\ 1 ]$であり、総和は $2$ です。

いずれも長さ $N$ の a または b からなる文字列として考えられる LCP array の総和として最小の値となります。

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。