問題
考察
各色ごとで文字列を右に1つ巡回シフトするとどのような文字列になるかという問題です。もし、仮に全ての文字が1色だった場合、答えとなる文字列の$i$文字目は下記のようになるはずです。($n\%m$はnをmで割った余り)
$$(S_i - 1 + N) \% N$$
上記の式は、下記の式に言い換えることもできます。
$$(S_{色1の出現回数} - 1 + (色1の個数)) \% (色1の個数)$$
このことから、もし1色だった場合、下記のことが分かれば$i$番目の文字が分かります。
- 色1が何回出現したか
- 色1が全部で何個あるか
もし色が複数ある場合でも、色毎に分けて考えればいいです。
そこで下記のような配列を用意しておきます。
$$V_{x,y} :文字列Sに対して、色xがy回出現した時の文字$$
上記の配列は文字列$S$とその時の色を順番に調べれば作成できます。
これを作成できれば、$i$番目の色が$x$だった場合、下記の式でその文字が分かります。
$$V_{x, ((色xの出現回数) - 1 + (色xの個数)) \% (色xの個数)}$$
つまり、下記の2点を求めることができれば答えが出せます。
- 色$x$が何回出現したか
- 色$x$が全部で何個あるか
色$x$の個数は、$V_x$のサイズを調べれば求めることができます。出現回数も各色毎の出現回数を管理する配列を事前に用意しておけば求められます。
結果として$i$番目の文字を求めることができるため、答えを出力することができます。計算量も$O(N)$と、十分に間に合います。
提出コード(コンテスト後)
ご不明点などがあれば教えていただけると幸いです。