Ordering5時間45分かけてようやく解けた。Ordering問題N頂点M辺の無向グラフがあり、辺には0からM-1までの番号が付いている。0番からN-2番までの辺は全域木をなすことが保証されている。これらに1からMまでの整数の重みを付けた重み付き無向グラフを考える。ある重み付けについて、それの最小全域木が0番からN-2番までの辺でできた木であるような場合、その重み付けを妥当な重み付けと呼ぶ。妥当な重み付けすべてについて、そのときの最小全域木の重みの総和を求めよ。解法Tを、0番からN-2番までの辺からなる全域木とする。妥当な重み付けがどのような性質を満たすべきかを考える。e_kの重みは全てeの重み未満である。ここで、本来の問題を簡略化した問題を考える。同じテクニックが使える。1は自明である(空を並べる方法は1通りであり、これはトポロジカルソート)。Sに新しい辺eを追加するときを考える。ints[S]本ある。(全体の長さ)である。以上で妥当な重み付けの総数のM!に対する割合が、したがって妥当な重み付けの総数がわかった。妥当な重み付けについて、0番からN-2番までの辺についた重みの合計の総和が知りたいのだった。これを求めるために、以下の部分問題を解く必要がある。この列にy人がランダムに入る。ランダムに入った後の自分の左から数えた位置の期待値を求めよ。kが固定値である場合(自分が必ずk番目にいる場合)を考える。