きままにものづくり

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

POJ 2549 : Sumsets

問題

要素数N(N \leq 1000)の数列が与えられる。この中でa+b+c=dを満たす最大のdを求めよ。

解法

a+bを全列挙し、d-cを二分探索する。a+bで選んだ要素とd-cで選んだ要素は互いに違わなければならない。値と共に、インデックスを持たせることで同じ要素を使ってる場合を除外する。

計算量

O(N^2logN^2)
N : 要素数

コード

広告を非表示にする