美術館の「鎖」について
この場合。
各赤線部分に対して高々1個しか明かりが入らないので、
緑部分には高々3個しか明かりが入らない。
ところで、各数字の周りの水色部分にはそれぞれ1個ずつ明かりが入るので、水色部分には合計でちょうど3個の明かりが入る。
よって、緑部分には少なくとも3個以上の明かりが入る。緑部分には高々3個しか明かりが入らないことを合わせて考えると緑部分にはちょうど3個の明かりが入ることが分かる。この3個は水色部分に入るもので尽くされるので、
この「緑部分だが水色部分でないところ」に点が打てる。
この場合。
各赤線部分に対して高々1個しか明かりが入らないので、
緑部分には高々8個しか明かりが入らない。(線が交差するのでさっきより難しく見えるが同じ話)
ところで、各数字の周りの水色部分にはそれぞれ2個ずつ明かりが入るので、水色部分には合計でちょうど8個の明かりが入る。
よって、緑部分には少なくとも8個以上の明かりが入る。緑部分には高々8個しか明かりが入らないことを合わせて考えると緑部分にはちょうど8個の明かりが入ることが分かる。この8個は水色部分に入るもので尽くされるので、
この「緑部分だが水色部分でないところ」に点が打てる。
ABC097-C - K-th Substring
与えられた文字列の部分文字列のうち辞書順でk番目のものを出力する問題です。
解法のソース
自分が思いついた解法
Submission #3501613 - AtCoder Beginner Contest 097
editorialを参考にした解法
Submission #3501551 - AtCoder Beginner Contest 097
自分が思いついた解法の考え方
以下1-indexedで考えてください。また、例としてサンプル2を使います。
atcoderandatcodeer
5
まず、文字列内の文字のポインタをすべてテーブルに入れます。ここで文字のポインタは、その文字からsの最後の文字までの文字列を意味しているため、次のようにならんでいるとみなせます。
1:atcoderandatcodeer
2:tcoderandatcodeer
3:coderandatcodeer
...
今、任意のn, mに対してn文字目から始まるm文字の部分文字列(以下s_n_m)は、n個目の文字列のm文字目までと言い換えられます。
そして、これらの文字列が辞書順になるようにポインタを並べ替えます。例で言うと、
1:andatcodeer
2:atcodeer
3:atcoderandatcodeer
4:codeer
...
といった具合です。
さて、今辞書順で一番小さい(以下、小さい)文字列はs_n_1です。何故なら、一番小さい文字列は一番小さい文字一文字の文字列であり、辞書順とは1文字目が一番小さいものを一番最初に持ってくる並べ方だからです。
次に、2番目に小さい文字列を探します。これは、1番目に小さい文字列に1文字付けくわえたものが理想的です。何故なら、1文字目を変えた文字列よりも2文字目を変えた文字列のほうが小さいからです。同様にn番目に小さい文字列もn-1番目に小さい文字列に1文字付けくわえたものが理想的となります。例で言うと
a
an
and
...
といった具合です。
しかし、このようにしていくといずれ文字列の最後まで達します。このとき、s_1_mとして作れる文字列は作り切ったことになるので、これ以降はs_2_mからs|s|mの中で最小の文字列を作ればいいということになります。これは先ほどと同様に考えればよいのですが、ここで文字列の重複を考える必要があります。具体的に言えば先頭から1つめの文字列と2つ目の文字列のi文字目までが一致していた場合、最小の文字列はi + 1文字の文字列とする必要があるということです。同様にして、3つ目の文字列についても考えていけます。例で言うと、
...
andatcodeer
at
atc
...
atcodeer
atcoder
atcodera
...
といった具合です。
このようにしてk番目に小さい文字列を求めることができます。計算量はソートがボトルネックになってO(|s|^2log|s|)となります。
補足
例えば"aa"といった文字列の場合、
1:a
2:aa
となりますが、この場合は1つ目の文字列の2文字目には実際は'\0'(<'a')が入っているため、他と同様に扱えます。
制約のとおりk<=5の場合、editorialの満点解法と上の解法を組み合わせてO(k|s|log|s|)の解法も可能だと思われます。またkの制約がない場合でも計算量がO(|s|^2log|s|+k)となるため対応できると思われます。
