AOJ 1522 - Planarian Regeneration - ツバサの備忘録

問題
 提出コード
数ヶ月放置してから考察しなおしたらすんなりいきました。
解説がなくてわからない問題は寝かせるのも大事だと思います。

解法

まず、サンプルケースなどを利用して手元で計算すると、
(縦における原点からの距離×縦の辺の長さ、の総和)×(横における原点からの距離×横の長さ、の総和)
のように、縦と横にわけて考えてから、最後に積をとると答えになることがただちにわかります。
縦と横でやっていることは同じなので、あとは1方向に対しての求め方を探ればよいです。
具体例として、2:3で $x$ 回切るパターンについて考えます。
初期状態は、(原点からの距離,辺の長さ)のペアは(1,1)の一つのみです。
1回切ると、
(1,2/5)と(3/5,3/5)に分かれます。
2回きると、
(1,4/25)、(21/25,6/25)、(15/25,6/25)、(9/25,9/25)の4つに分かれます。
全ての部分を2つに切っていくので、 $x$ 回切ったとき、 $2^{x}$ 個の辺ができます。
また、 $m:n$ に切断していくとき、現在辺の長さが $p$ の部分を切ると、あたりまえですが
$p×\frac{m}{m+n}$ と $p×\frac{n}{m+n}$ の2つに分かれます。辺は最初1ですので、全ての辺は

$m:n$ で $x$ 回切断するうち、何回 $n$ を選んだか

という回数で場合分けをすることが可能です。
$cnt[i][j] = i$ 回切断したときに、 $j$ 回 $n$ を選んだものの個数
とすると、
$cnt[i][j] = cnt[i-1][j] + cnt[i-1][j-1]$
となります。
次に、 $j$ 回 $n$ を選んだ場合の長さを求めます。
$dis[i][j] = i$ 回切断したときに、 $j$ 回 $n$ を選んだものの辺の長さ
とすると、
$dis[i][j] = \left\{ \begin{array}{} dis[i-1][j]×\frac{m}{m+n}　( i> j)\\ dis[i-1][j]×\frac{n}{m+n}　(i \leqq j) \end{array} \right.$
となります。
辺の長さが出せたので、あとは原点からの距離を求めれば終わりになります。
先ほどの続きとして、現在辺の長さが $p$ であり、原点からの距離が $q$ である部分についてみてみます。先ほども述べたように、これを $m:n$ で切ると $\frac{p×m}{m+n}$ と $\frac{p×n}{m+n}$ の2つに分かれます。このとき、長さが $\frac{p×m}{m+n}$ になった辺は、原点からの距離は $q$ のままであり、もう片方の辺の原点からの距離は、 $q$ から左側の辺の長さ、すなわち $\frac{p×m}{m+n}$ だけ引いたものになります。
もうすこし見やすくすると、
今原点からの距離が $q$ の辺について、 $i-1$ 回までで $j$ 回 $n$ を選んで切断していた場合、次の切断をしたときに辺の原点からの距離は、

$m$ を選んだ側
$q$
$n$ を選んだ側
$q-dis[i][j]$

の2つに分かれます。
これを、 $n$ を選んだ回数ごとに距離を先に合計しておきます。
$sum[i][j] = i$ 回切断したときに $j$ 回 $n$ を選んだものの原点からの距離の合計
とすると、
$sum[i][j] = sum[i-1][j] + sum[i-1][j-1] - cnt[i-1][j-1]×dis[i][j-1]$
となります。
これで必要なものがそろったので、あとは
(原点からの距離)×(辺の長さ)
の総和を求めます。これは
$dis[x][j]×dis[x][j]$
を $j$ について全探索して合計していけば求まります。
最後に、縦と横それぞれについてこの操作を行い、かけあわせれば答えとなります。