簡単に見えて難しくそしてやっぱり簡単。
level1だと思って油断していたらとても難しかった。
TopCoder Statistics - Problem Statement
問題:牛がうるさい。とてもうるさい。解決法として、牧場にちらばっている牛を一匹だけ鳴かせることにした。牛たちは鳴き声が遠ければ遠いほど不快になる。x,y地点で牛が鳴くと、i,j地点にいる牛の不快度は(x-i)^2+(y-j)^2である。それぞれの牛の不快度の総和を求めて、最小のものを返せ。
文字列を検索して牛がいる座標x,yをそれぞれベクトルに保管。そしてx,yベクトルから数値を引っ張りだして計算する。
#include <iostream> #include <sstream> #include <string> #include <vector> #include <algorithm> #include <math.h> using namespace std; class MooingCows{ public: int beki(int a,int b){ for (int k=0;k<b;k++) a*=a; return a; } int dissatisfaction(vector <string> farmland){ int h,w,minmoo,moo=0; vector<int> fx; vector<int> fy; h=farmland.size(); w=farmland[0].size(); for (int y=0;y<h;y++){ for (int x=0;x<w;x++){ if(farmland[y][x]=='C'){ fx.push_back(x); fy.push_back(y); } cout<<farmland[y][x]<<" "; } cout<<endl; } for (int j=0;j<fy.size();j++){ moo=0; for (int i=0;i<fy.size();i++ ){ moo+=beki(fx[i]-fx[j],2)+beki(fy[i]-fy[j],2); // cout<<fx[i]<<" "<<fy[i]<<" "<<moo<<endl; } minmoo=min(minmoo,moo); } cout <<minmoo<<endl; return minmoo; } }; int main(){ MooingCows ob1; string a[] ={"CCC....", "C......", "....C.C", ".C.CC..", "C......"} ; //int a[]={6,8,5,4,7,4,2,3,1}; vector <string> tx(a,a+(sizeof(a)/sizeof(a[0]))); ob1.dissatisfaction(tx); return 0; }
- べき乗は^ではない。実数の場合はpowを使う。整数を引数にもつ場合は自分で関数を作るほうがいい。