http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=229&page=show_problem&problem=3150 問題 W*Hの盤面に図のように順番に番号を付け、1番から順に左上から順に並べ直す作業をする。この作業を何回やれば数値が1から順に並ぶ…

http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=242&page=show_problem&problem=3155 問題 長さnの順列でバブルソートをした時の交換回数の期待値を求めよ。 1 解法 数値のペアに着目すると2つの値は正順になっているか逆…

http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=242&page=show_problem&problem=3154 問題 長さnの数列Aと数値uが与えられる。次に[l,r]の範囲のv未満の数値の個数をkとした時に、a[p]をu*k/(r-l+1)にするクエリがm個来る…