きままにものづくり

日々の気付いたことなんかを書いてます。

SRM638Div1Medium

問題

サイズNの配列が与えられる。配列内の要素aとbの和がmaxSize以下である場合は、その二つの要素を交換することができる。この時の配列のパターンの総数を求めよ。

解法

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

計算量

 O(N^2)

コード

広告を非表示にする