Sumsets POJ2549

投稿日：2023/01/04 更新日:2023/01/04

POJ

競プロ

問題：http://poj.org/problem?id=2549

問題

整数の集合 $S$ が与えられる。そこから互いに異なる $a,b,c,d$ を選び $a+b+c = d$ を満たす最大の $d$ を求めてください

解法

半分列挙します。

$a+b+c = d$ は $a+b = d-c$ と変形できるので、左辺右辺でそれぞれ列挙していきます。先に左辺を列挙し、その後右辺を列挙する際に、二分探索で当てはまる左辺を見つけると良いです。

同じ要素を重複して選べないので、左辺を列挙する際に何番目の値を使用しているのかを記録しておきます。

実装

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

const int INF = 1e9 + 100;

struct Value{
    int v, id1, id2;
    bool operator<(const Value a) const {
        return v < a.v;
    }
};

void solve(int n){
    vector<int> s(n);
    for(int i = 0;i < n; ++i){
        cin >> s[i];
    }

    vector<Value> sum;
    for(int i = 0;i < n; ++i){
        for(int j = i+1;j < n; ++j){
            Value v;
            v.v = s[i] + s[j];
            v.id1 = i;
            v.id2 = j;
            sum.push_back(v);
        }
    }
    sort(sum.begin(), sum.end());

    typedef vector<Value>::iterator T;
    int ans = -INF;
    for(int i = 0;i < n; ++i){
        for(int j = 0;j < n; ++j){
            if(i == j)continue;
            Value v;
            v.v = s[j] - s[i];
            T start = lower_bound(sum.begin(), sum.end(), v);
            T end = upper_bound(sum.begin(), sum.end(), v);
            for(T itr = start; itr != end; ++itr){
                if(itr->id1 == i || itr->id2 == i ||
                   itr->id1 == j || itr->id2 == j){
                    continue;
                }
                ans = max(s[j], ans);
            }
        }
    }

    if(ans == -INF){
        cout << "no solution" << '\n';
    }else{
        cout << ans << '\n';
    }
}

int main(){
    ios::sync_with_stdio(false);
    std::cin.tie(0);
    int n;
    cin >> n;
    while(n != 0){
        solve(n);
        cin >> n;
    }
    return 0;
}