第10回日本情報オリンピック 本選(過去問)から、その提出コードの解答例です。
AtCoderとは、コンテストを通じて、プログラミングやアルゴリズムを学習するサービスです。
atcoder.jp
プログラミングコンテストとは、「与えられた問題をいかに素早く、正確に」解くことができるかを競うものです。
「競技プログラミング」を略して、「競プロ」などと呼ばれています。
#D - 歩くサンタクロース (Walking Santa)
https://www.ioi-jp.org/joi/2010/2011-ho-tasks_data/2011-ho.pdf#page=9
僕が作成、提出したコードは、以下のとおりです。
/* AtCoder Problems in C++ #D - 歩くサンタクロース (Walking Santa) https://www.ioi-jp.org/joi/2010/2011-ho-tasks_data/2011-ho.pdf#page=9 提出コードの解答例 https://neguse-atama.hatenablog.com */ #include<bits/stdc++.h> using namespace std; using ll=long long; int main(void){ ll h,w,n; cin>>h>>w>>n; vector<ll> x(n),y(n); for(ll i=0;i<n;i++){ cin>>x[i]>>y[i]; } vector<ll> X=x,Y=y; sort(X.begin(),X.end()); sort(Y.begin(),Y.end()); vector<ll> a,b; if(n%2==0){ a={X[n/2-1],X[n/2]}; b={Y[n/2-1],Y[n/2]}; }else{ a={X[n/2]}; b={Y[n/2]}; } ll ans=1e18; ll ax=-1,ay=-1; for(ll i : a){ for(ll j : b){ ll cnt=0; ll mx=0; for(ll k=0;k<n;k++){ cnt+=abs(i-x[k])+abs(j-y[k]); mx=max(mx,(ll)abs(i-x[k])+abs(j-y[k])); } if(ans>cnt*2-mx){ ans=cnt*2-mx; ax=i; ay=j; } } } cout<<ans<<endl; cout<<ax<<" "<<ay<<endl; return 0; }