問題概要
N人の生徒がいて、それぞれの名前はS_i。アルファベットの並び順をランダムに決めて辞書順にソートした時、indexの期待値はどうなるかをそれぞれの生徒について求めよ。
解法
この問題は、文字列アルゴリズムでも解けるが、もっと簡潔な解法がある。abc...という通常の順番とzyx...という反転した順番でソートして、それぞれの場合でindexを求めて平均をとれば解ける。
解説
2つの（異なる）文字列a, bに対し、辞書順は以下のようなアルゴリズムで決定される。一般性を失わず、|a| <= |b| とする。 ①1 <= i <= |a| かつ a[i] != b[i] であるようなiがあるとき、その中で最小のものjをとってa[j] < b[j]ならa < b、a[j] > b[j]ならa > bとする。 ②①でiがとれなかったなら、bが辞書順で大きいとする。
①の場合、アルファベットの並び順によって順序が変わってくる。具体的には、決めた並び順でa[j]とb[j]のどちらが先に出てくるかによって順序が変わる。よって、アルファベットの並び替えで2要素のうちどちらが先に来るかにのみ注目すればいい。
②の場合、アルファベットの順番は順序に関係がない。よって、並び方によらずどちらが後ろが決定する。
さて、indexの期待値は、「ソートした時自分より前に来る文字列の期待値」と言い換えることができる。（正確にはそれより1大きくなる） まず、1つのペアa, bに着目して、a < b となるようなアルファベット順が選ばれる確率を考える。期待値の線形性より、これをbを含む全ペアに対して計算できればbに対する答えがわかる。 さて、abc...の並び順でbより小さくなる要素がx個、zyx...の並び順ではy個だったとする。このとき、①のケースで順序が決まるものが|y - x| 個あったということになる。（反対に、②のケースで決まるものはmin(x, y) 個。）①のケースの寄与は、順列でどちらのアルファベットが先に来るかのみで決まるので1/2、②のケースは1（全部同じなので）寄与する。よって、期待値は|y - x| / 2 + min(x, y) となる。計算すると、これは (x + y) / 2 に一致する。よって、平均を取ることで正しい答えが求まることが分かった。
感想
合宿前全然寝れなかったので怪文書を生成
