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