TopCoder SRM 821 : Div1 Easy Div2 Medium OneBattleship

Div1 EasyとDiv2 Mediumが同じ問題になるの久しぶり。
https://community.topcoder.com/stat?c=problem_statement&pm=17350

問題

グリッドが与えられる。
ここで、1*3のサイズを占める敵の軍艦を探すゲームを行う。
一部のマスは、軍艦がないことが確定している。

いくつかのマスに砲撃を行い、軍艦のうち最低1マスを破壊したい。
砲撃できる箇所が、未確定マスの1/3までの時、条件を満たす破壊の仕方を答えよ。

解法

各セルを(列+行)%3で分類すると、軍艦がどこにあっても、各分類を1マスずつ含むことになる。
そこで、どこか1つの分類に対応する全セルを砲撃すれば、必ず条件を満たす。
なので、未確定マスが最小となる分類の全セルを攻撃すれば、マス数の条件を満たせる。

class OneBattleship {
	public:
	vector <string> hit(vector <string> grid) {
		int C[3]={};
		int H=grid.size();
		int W=grid[0].size();
		int y,x;
		FOR(y,H) FOR(x,W) if(grid[y][x]=='.') C[(y+x)%3]++;
		int tar=0;
		if(C[1]<C[0]) tar=1;
		if(C[2]<C[tar]) tar=2;
		FOR(y,H) FOR(x,W) if(grid[y][x]=='.'&&(y+x)%3==tar) grid[y][x]='*';
		return grid;
		
	}
}

まとめ

まぁ簡単目なのでDiv2側はMediumになったのかな。