SRM638Div1Medium
問題
サイズNの配列が与えられる。配列内の要素aとbの和がmaxSize以下である場合は、その二つの要素を交換することができる。この時の配列のパターンの総数を求めよ。
解法
動的計画法で答えは求まる。
配列のパターンの総数を計算する関数をfとする。
配列内の最大値と最小値の和がmaxSize以下の場合は最小値はどの値とも交換可能なので、この時のパターンの総数は
となる。ここで、Aは元の配列、BはAから最小値の要素を除いた配列、|A|はAの要素数である。
配列内の最大値と最小値の和がmaxSizeより大きい場合は、最大値の要素は動かすことができないので、その要素を中心に二つの配列に分割して、計算を行う。
ここで、は最大要素を中心に左側の配列、
は右側の配列を示す。
配列を分割せずに、最大要素を削除しただけで計算した場合、要素数が違うパターンも余分に数えてしまうことになる。
例として、元のパターンが
1 2 a 5 6
であるとする。ここで、aは最大要素を示し動かすことができないものとする。
ここで、aを削除した配列をfに渡してしまうと、
1 2 5 a 6
のような場合も計算してしまう。
計算量
