【 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