【AOJ 2300】Calendar Colors

問題

Calender Colors | Aizu Online Judge

方針

• N個のLABカラーが与えられる.
• そこからM個取り出し, 要素それぞれの差の二乗の和を求める.
• その和の最大値が答え.
• であることから全探索しても良さそう.
• M個取り出すときにbitを使うと便利っぽい.

コード

#include <iostream>
#include <vector>
#include <cmath>
#include <cstdio>
#include <algorithm>
 
using namespace std;
 
#define rep(i,n) REP(i,0,n)
#define REP(i,a,n) for(int i = a ; i < (int)n ; i++)
 
struct LAB{
  double l, a, b;
  LAB(double ln, double an, double bn){
    l = ln; a = an; b = bn;
  }
};
 
int main(){
  int n, m;
  double l, a, b;
  vector<LAB> v;
  
  scanf("%d %d", &n, &m);
  rep(i, n){
    scanf("%lf %lf %lf", &l, &a, &b);
    v.push_back(LAB(l,a,b));
  }
   
  double ans = -1;
  rep(i, (1<<n)){
    vector<LAB> elem;
    rep(j, n){
      if(i & (1 << j)){
        elem.push_back(v[j]);
      }
    }
 
    if((int)elem.size() != m) continue; 
     
    double tmp = 0;
    rep(i, m-1){
      REP(j, i+1, m){
        tmp += (pow(elem[i].l-elem[j].l, 2) + pow(elem[i].a-elem[j].a, 2) + pow(elem[i].b-elem[j].b, 2));
      }
    }
    ans = max(ans, tmp);
  }

  printf("%.8f\n", ans);
}

参考

AOJ 2300 - Calendar Colors - プログラミングコンテストの記録