atcoder#ABC280H. [ABC280Ex] Substring Sort
[ABC280Ex] Substring Sort
配点 : 点
問題文
個の文字列 が与えられます。 $M = \displaystyle\sum_{i=1}^N \frac{|S_i|(|S_i|+1)}{2}$ とおきます。 また、文字列 と整数 に対し、 で の 文字目から 文字目までの文字からなる部分文字列を表します。
整数の三つ組からなる長さ の列 $((K_1, L_1, R_1), (K_2, L_2, R_2), \ldots, (K_M, L_M, R_M))$ は以下の条件をみたします:
- 個の要素は相異なる。
- すべての に対して、 かつ である。
- すべての に対して、辞書順で である。
以上 以下の整数 個 が与えられます。各 に対して、 としてあり得るものを つずつ求めてください。なお、条件をみたす三つ組の列が必ず つ以上存在することが証明できます。条件をみたす三つ組が複数存在する場合、どれを出力しても構いません。また、異なる の間で、条件をみたす三つ組の列が共通のものである必要もありません。
辞書順とは
2 つの文字列 S, T が以下の条件のいずれかをみたすとき、かつそのときに限り、辞書順で S \leq T であると言います。- |S| \leq |T| かつ S = T[1, |S|] である。
- ある 1\leq k\leq \min(|S|, |T|) が存在し、1\leq i\leq k-1 について、S と T の i 文字目は等しく、S の k 文字目は T の k 文字目よりアルファベット順で真に小さい。
制約
- $\displaystyle\sum_{i=1}^N \lvert S_i\rvert\leq 10^5$
- $1 \leq x_1
- は整数
- は英小文字のみからなる文字列
入力
入力は以下の形式で標準入力から与えられる。
出力
行出力せよ。 行目には、条件をみたす としてあり得るものを空白区切りで出力せよ。 条件をみたす三つ組が複数存在する場合、どれを出力してもよい。
2
abab
cab
2
5 14
1 3 4
2 1 1
であり、条件をみたす三つ組の列としては、
$(1,1,1), (1,3,3), (2,2,2), (1,1,2), (1,3,4), (2,2,3), (1,1,3), (1,1,4), (1,2,2), (1,4,4), (2,3,3), (1,2,3), (1,2,4), (2,1,1), (2,1,2), (2,1,3)$ が考えられます。
この順で並べた時の に対応する の列は、(a
, a
, a
, ab
, ab
, ab
, aba
, abab
, b
, b
, b
, ba
, bab
, c
, ca
, cab
)となります。
なお、 番目の要素 を、 番目や 番目の要素と入れ替えた列も条件をみたすため、 も正解となります。
3
a
a
ba
2
1 2
1 1 1
1 1 1
であり、条件をみたす三つ組の列としては、 や が考えられます。
出力する について、 番目の要素が であるような条件をみたす列は異なる の間で共通のものである必要が ない、 すなわち、「任意の について 番目の要素が である」 ような列は 必ずしも存在する必要がない ことに注意してください。
10
gxgpuamkx
szhkbpphykin
ezplvfja
mopodotkrj
rimlvumuar
nexcfyce
eurgvjyos
dhvuyfvt
nrdyluacvra
ggwnpnzij
6
74 268 310 380 455 489
3 1 2
4 4 5
4 3 7
9 6 6
6 6 6
2 2 12