読者です 読者をやめる 読者になる 読者になる

SRM 708 DIV1 Easy: BalancedStrings

文字列s[0]~s[N-1]の文字列の末尾に文字追加して解を構成すことを考える。
ある文字列s[i]に文字を追加したときに全体で、instabilityは0~1、similarityは0~100*(N-1)増加する。
このようにinstabilityの値のほうが調整がし易い。
そこでまずsimilarityが小さくなるようにざっくりs[0]~s[N-1]を作ってinstabilityをインクリメントしていく。
similarityを小さくするにはできるだけs[0]~s[N-1]が文字を共有しないでほしいので以下のような簡単な構成が思いつく。
すなわち
s[i] = 'a' + (i mod 26)
この種の構成法について
N=100 の一番面倒な場合についてだけ考えてみる。
i番目の文字列についてj<iでかつs[i] = s[j]であるものはj/26 個ある。
これでsimilarityは数えられた。|s[i]| = 1 よりinstability=0。
similarityに追いつくようinstabilityを増やしていけばよいのだが、similarityの増加の仕方が厄介そうなのは明らか。
similarityが定まったら、similarityを増加させないでinstabilityを調整できれば楽なのだが、そのような構成法はあるだろうか。
ある。実は今まで使っていない文字が2種類以上あるならば、単にその2文字(仮にA,Bとすると)
s[0] + A + B + A + B ... (100文字まで)
のようにAとBを末尾に追加すればよい。
同様に未使用の文字CとDがあるとして
s[1] + C + D + C + D ....(100文字まで)
未使用の文字が必要だったので
s[i]の構成を
s[i] = 'a' + (i mod M) (M<26)に変更しよう。
N=100のときにinstabilityが最大になるのは明らかで、未使用の文字の種類が最大になる。
このときM=22とすると都合がいい。すなわちw,x,y,zの4文字でinstabilityを調整する。
最終的に解は
s[0] = awxwxwxwx...
s[1] = byzyzyzyz...
s[2] = c
s[3] = d
...
のような形になる。