SRM 638 DIV1 Medium: NarrowPassage2

解法は簡単だが思いつけないタイプ

解法

分割統治法、再帰

 

maxSizeSum=10で色々やってみる。

m = min(size), M = max(size)

とする。

size = {5,2,3,4,6}

のような場合

m = 2, M = 6

であり、

m+M <= maxSizeSumが成り立つので

2はどこにでもおける。

すなわち、2の各位置について、他の要素の並べ方は別々に考えることができる。

つまり

size' = {5,3,4,6}

 の並べ方1通りに対して、2を好きな箇所に挿入でき、挿入できる位置は|size|通り。

これで部分問題

count(size', maxSizeSum)

が得られた。

今度はm+M > maxSizeSum のときを考える。

size = {3,2,5,9,4,6}

とすると

m = 2, M = 9

であり m + M = 11 > maxSizeSum

Mに隣接する値は常にm以上であるはずだから、Mを隣接する値と交換することはできない。つまり、Mの位置は固定された。また、Mより左にある要素はMより右へは行けない。同様にMより右にある要素はMより左へはいけない。なので数列から値がMである要素を一つ取り除いて

left = {3,2,5}, right = {4, 6}

 のようにMの左右の列は別々に並び替えることができる。

よって

部分問題

count(size, maxSizeSum) = count(left, maxSizeSum) * count(right, maxSizeSum)

であり、

もとの問題は部分問題

count(left,maxSizeSum)とcount(right, maxSizeSum)に分割することができた。

最後に再帰の底を考えると、|size|<=1で並べ方は1通りしかない。

思いつきたかった

最小値や最大値が特異な動きをするのは簡単に思いつけそう。少し手を動かして実験をしてみれば、最小値が自由に動ける場合や最大値が固定される場合に気づく?もし最大値が固定される場合に気づけば、その場合は部分問題に分割できることは明らか。そうでない場合を考えてみる。こちらも部分問題に分割できる。分割統治法。あとは再帰の形で表せればいい。