一日1solve

どうもー　きゃらっぱーです。きゃっとあっぱーでーす。
waterとか"t"の発音って"r"にかえたらネイティブっぽいよね。わらー。わらーめろん。
そんなことは置いといて。
最近ネタの枯渇で困っているという私のもとに、あるアイデアが思いついた。
「ネタがないなら、精進すればいいじゃない」
私はインスピレーションを感じた。「なんていい言葉だ。持ちネタにしよう」と。
というわけでネタが無いので1日1solve。
自分で問題選んでもあれなんで、AOJのサイトを開いてTOPに出てくるrecent activityのなかで一番上にあるAcceptの問題を解いていきたいと思います。
今回はAOJ0529。
矢が４本っていうのが、ヌルゲー感を醸し出しますが、私は動じない。ヌルゲーだろうとsolveしよう。更新のために。

#include<stdio.h>
#include<algorithm>
#include<vector>
using namespace std;
int main(){
    int a,b,mato[1000];
    vector<int> nums;
    while(scanf("%d%d",&a,&b),a,b){
        int res=0;
        nums.clear();
        for(int i=0;i<a;i++)scanf("%d",mato+i);
        for(int i=0;i<=a;i++)
            for(int j=0;j<=a;j++)
                nums.push_back(mato[i]*!!(i-a)+mato[j]*!!(j-a));
                
        sort(nums.begin(),nums.end());
        vector<int>::iterator it=nums.begin();
        while(it!=nums.end() && b>=*it){
            vector<int>::iterator itt=upper_bound(nums.begin(),nums.end(),b-*it);
            res=max(res,*it+++*--itt);
        }
        printf("%d\n",res);
    }
    return 0;
}

いやー　気づいたら気持ち悪い式書いてるのは仕様です。
アルゴリズムを平たく言うと、2つづつに分けたのを足すだけです。オーダーはN*N*logNですかね。upper_boundのアルゴリズムは２分探索だと期待しましょう。
そんなに難しくないですね。４つですから。
これ多くなると解けるのでしょうかねー。今度ちょっとやってみますー。

それでは今日の分ー。

ではまたあしたー