読者です 読者をやめる 読者になる 読者になる

【 CodeIQ 】ホリエモンからの挑戦 解いてみた

挑戦者求む!あなたが優秀なエンジニアなら必ず解けるはずです。挑戦お待ちしています。 by SNS株式会社 堀江貴文│CodeIQ
ホリエモンからの賞金問題といてみましたヾ(@⌒ー⌒@)ノ

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main(){
	int len = 0;
	int n = 0;
	int ans = 0;
	int p = 0;
	cin >> len >> n;
	vector <int> dat(n);
	for(int i=0 ; i<n ; i++){
		cin >> dat[i];
	}
	sort( dat.begin(), dat.end(), greater<int>() );
	while(p <= n-3){
		if(dat[p] >= len){
			p++;
			continue;
		}
		int p2 = p+1;
		while(p2 <= n-2){
			if(dat[p]+dat[p2] >= len){
				p2++;
				continue;
			}
			bool f=binary_search(
				dat.begin()+p2+1, dat.end(), len-dat[p]-dat[p2], greater<int>()
			);
			if(f){
				ans++;
			}
			p2++;
		}
		p++;
	}
	cout << ans << endl;
	return 0;
}

降順ソートした後、明らかに違うの切りながら2つを選んで残り1つを二分探索しました。
おそらく想定された方法かなって感じがします。codeiq.jp