最強最速アルゴリズマー養成講座をやってみる

いきなりDiv.1のMediumとかだされたりしてなんとなく遠ざけてたけど、Div.1Easyとかぐらいなら解けるようになったし、レベル上げたいしやってみた。

石並べ

第四回の問題。
僕は単純に思いついたとおり貪欲で書いたけど、口座にはもっとエレガントな解き方が乗っているので要参考。
本番でやるときどっちでやったほうが早いかは思考力とタイピングスピード比べることになるから知らない。

class NotTwo {
public:
int maxStones(int width, int height) {
  //ここにプログラムを入力！
  int dx[] = { -2,0,0,2 };
  int dy[] = { 0,-2,2,0 };
  vector<vector<int> > map;
  for (int i=0; i<height; i++) 
    {
      vector<int> col(width,-1);
      map.push_back(col);
    }
  for (int i=0; i<height; i++) 
    {
      for (int j=0; j<width; j++)
	{
	  if (map[i][j]==-1) 
	    {
	      map[i][j]=1;
	      for (int k=0; k<4; k++)
		{
		  if (dx[k]+j<width && dx[k]+j>=0 && dy[k]+i<height && dy[k]+i>=0) map[dy[k]+i][dx[k]+j]=0;
	        }
	     }
	}
     }
     int sum=0;
     for (int i=0;i<height; i++) for (int j=0; j<width; j++) sum+=map[i][j];
     return sum;
}

emacsの自動インデントが頭悪い

人とウサギとモンスター

第三回の問題か…いや、第四回の最初のページで紹介されてる問題かな？
TopCoderからやってみたときに「二行で書ける」とあったのでひらめきで思いついたものを二行で実装してみたら本当に通ったｗ

class MonstersAndBunnies {
public:
  double survivalProbability( int M, int B ) {
    if (M%2==0) return 1.0/(M+1.0);
    else return 0.0;
  }
};

この他の問題は難しいので出来ませんでした○