Google Code Jam 2015 Round 1C : A. Brattleship

GCJ Round1Cは1Bより簡単だったみたい。
https://code.google.com/codejam/contest/4244486/dashboard#s=p0

問題

サイズR*Cのグリッドを用いた戦艦ゲームを考える。
相手は、ここに縦1マス横Wマスの戦艦を1箇所配置する(90度回転は不可)。

プレイヤーはどこかのマスを指定して攻撃すると、相手はそれが戦艦の一部にヒットしたかどうかを答えてくれる。
相手は任意のタイミングで戦艦の位置を変更できる。
ただし、過去回答したヒット/ミスの位置と矛盾するような場所には移動できない。

プレイヤーが戦艦を確実に撃沈する(Wマスすべてに1回以上攻撃する)には、最低何回攻撃すればよいか。

解法

仮に1発攻撃が当たった場合、最大でもあとW発で勝負がつく。
例えば当たった場所からだんだん左に攻撃していって、外れたマスが1回あればその右Wマスで戦艦の位置が確定する。

よって、相手はとにかく1発目が当たらないように逃げまくると考えて良い。
まず、プレイヤーはR行のうち(R-1)行から逃げ場をなくす。
逃げ場をなくすには、左からWマス目、2Wマス目…とWマスごとに攻撃すればよいので、1行あたり(C/W)回攻撃すればその行には戦艦がいられなくなる。

最後の1行についても、残りが2W-1マス以下になるまで左からWマスごとに攻撃して行く。
残り2W-1マス以下になれば、真ん中のマスは必ず攻撃がヒットするので最初の推論によりW+1回の攻撃で戦艦を撃沈できる。
ただし、残りマスがWマスちょうどの場合は、戦艦の位置は確定するのでW回の攻撃で良い。

void solve(int _loop) {
	int f,i,j,k,l,x,y;
	int R,C,W;
	
	cin>>R>>C>>W;
	int miscol = (R-1)*(C/W);
	
	while(C>=2*W) miscol++, C-=W;
	
	if(C==W) miscol+=W;
	else miscol+=W+1;
	
	_P("Case #%d: %d\n",_loop, miscol);
}

まとめ

戦艦ゲーム、PCでプレイしたことはあったけど、元はテーブルゲームだったのね。
これ戦艦の大きさが1*WじゃなくてC*Wだったらどうなるのかな。