diverta 2019 Programming Contest 2 B問題

B - Picking Up

2019年6月15日開催のdiverta 2019 Programming Contest 2 に参加した．B問題の私の理解と解説．

B - Picking Up

問題はこちら．j番目のボールの座標からi番目のボールの座標へのベクトル(i<j)を全て調べて，出現回数が一番多いベクトルを(p, q)とすれば最小コストでの移動が可能になる．ただし，移動の順序は自由なので，逆向きでもよいことに注意する．

C++の実装例(#include は省略)

#define rep(i,n) for(long long i=0;i<n;i++)
using namespace std;

int main() {
 int N;
 cin >> N;
 vector<int> x(N), y(N);
 
 if(N==1) { // Nが1のときは，コスト1で確定．
   cout << 1 << endl;
   return 0;
 }
 
 rep(i, N) {
   cin >> x[i] >> y[i];
 }
 
 // ベクトルの集合を得る．
 int tmpx = 0;
 int tmpy = 0;
 priority_queue<pair<int, int>> vec;

 for(int i=0; i<N; i++) {
   for(int j=i+1; j<N; j++) {
     tmpx = x[i] - x[j];
     if(tmpx>0) { // xが正
       vec.push(make_pair(tmpx, y[i]-y[j]));
     } else if(tmpx==0){ // tmpx がゼロ なら y が正になるようにする．
       tmpy = y[i]-y[j];
       if(tmpy>0) vec.push(make_pair(tmpx, tmpy));
       else vec.push(make_pair(-tmpx, -tmpy));
     } else { // tmpx が負: xが正になるようにする．
       vec.push(make_pair(-tmpx, -y[i]+y[j]));
     }
   }
 }
 
 // 出現したベクトルから最頻数を求める
 int cnt = 0;
 int maxcnt = 0;
 pair<int, int> tmp_p = make_pair(0, 0);
 int vecsize = N*(N-1)/2;
 rep(i, vecsize) {
   pair<int, int> p = vec.top();
   vec.pop();
   if(tmp_p.first==p.first && tmp_p.second==p.second){
     cnt++; // 同じものが連続で現れたらカウントプラス
   } 
   else { //違うものが現れたら，maxか判定し，tmp_pを更新, cntをリセット
     if(cnt>maxcnt) maxcnt = cnt;
     tmp_p.first = p.first;
     tmp_p.second = p.second;
     cnt = 0;
   }
 }
 if(cnt>maxcnt) maxcnt = cnt; // 最後のベクトルがmaxか確認．
 cout << N-maxcnt-1 << endl;
 
 return 0;
}

上の実装の"//ベクトルの集合を得る"の部分では，j番目のボールの座標からi番目のボールの座標へのベクトル(i<j)を，x成分が0以外ならプラスになるように，x成分が0ならy成分がプラスになるように，方向をさだめて，priority_queue に格納することで，逆方向も含めた同じベクトルが連続して出てくるようにしている．priority_queue は格納した要素を昇順に(複数成分のときは第一成分から優先して)並べ替えて格納してくれるqueueである．例えば，そのまま(x[i]-x[j], y[i]-y[j])のとき，

(1,0) (0,1) (1,2) (-1,0) (0,-1) (0,-2)

となるものを，

(1,2) (1,0) (1,0) (0,2) (0,1) (0,1)

としている．これにより，ベクトルの出現個数を調べる際の計算を速くしている(本問題ではここまでしなくても計算時間は十分間に合う．この実装だと実行時間は1ms)．

後半の" // 出現したベクトルから最頻数を求める"部分では，先ほど紹介した，

(1,2) (1,0) (1,0) (0,2) (0,1) (0,1)

のようなpriority_queueを順番に見ていき，連続して同じベクトルが出てきた回数の最大値を maxcnt に格納している．