読者です 読者をやめる 読者になる 読者になる

マトリョーシカ的日常

ワクワクばらまく明日のブログ。

牛を呼び覚ます呪文(SRM 314 div2 level1)

簡単に見えて難しくそしてやっぱり簡単。

http://instagram.com/p/XwCxBxBBDZ/

 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を使う。整数を引数にもつ場合は自分で関数を作るほうがいい。