JOI2008本選 問題3@C++(31)
去年は解けなかった問題。歯が立たなかったので復讐。
upper_boundとlower_boundとequal_rangeとbinary_searchの使い方を覚えた。
ところでこの関数群はset,multiset,map,multimapには独自で用意されているらしい。いいねえ。
/* TASKNO: 3 LANG: C++ NAME: Masaki Hara J */ #include <cstdio> #include <algorithm> #include <vector> using namespace std; int main(int argc,char* argv[]) { FILE* in=fopen("input.txt","r"); FILE* out=fopen("output.txt","w"); int n,m; fscanf(in,"%d %d\n",&n,&m); vector<int> points(n+1); points[0]=0; for(int i=0;i<n;i++) { fscanf(in,"%d\n",&points[i+1]); } sort(points.begin(),points.end()); vector<int> points_double; for(vector<int>::iterator i=points.begin();i!=points.end();++i) { for(vector<int>::iterator j=i;j!=points.end();++j) { int sum=*i+*j; if(sum>m)break; points_double.push_back(sum); } } sort(points_double.begin(),points_double.end()); int current_max=0; for(vector<int>::iterator i=points_double.begin();i!=points_double.end();++i) { vector<int>::iterator over_bound=upper_bound(points_double.begin(),points_double.end(),m-*i); if(over_bound!=points_double.begin()) { current_max=max(current_max,*(over_bound-1)+*i); } } fprintf(out,"%d\n",current_max); fclose(out); fclose(in); return 0; }
追記。掲示板(http://jbbs.livedoor.jp/computer/38153/)からリンクして来てもらっているようなので説明します。
頭良い!
まず、一番目に0点を入れて、後ろに全てのデータを配列に置く。で、ソート。
一番最初に0があるので、それはその回は投げないということである。
で、次にそのデータを全てそれぞれ足した、配列を用意する。
で、ソート。
これで、二回投げたときに得られる全ての値を得られる。
よって、次に最大の値から一つの値を引いて、それを超えない値を探す。
で、一つ上の行を二回投げたときに得られる全ての値について演算すると上のようになると。
素晴らしい。
褒めてもらってるところ恐縮なのですが、実はこれ、本選終了後に解説された公式の解答なんです・・・