GCJ 2015 Round 1C A. Brattleship

問題

問題文

$R \times C$ マスのグリッドがあり，兄と弟がゲームをしている． グリッドの一部には，ある横一列に並んだ $1 \times W$ の部分 (船) がある． 兄は目隠しをしてこの部分を全て特定しようとしている． 兄ができるのは，「ある 1 つのマスが船に覆われている？」という弟に対する質問で， 弟はこれに Yes か No で答えなければならない． 兄の目的は，船をつくる $W$ マス全てに対して質問し Yes と言わせることである． ところが，弟は過去の兄との応答に矛盾しない範囲で， 兄に気付かれないように船の位置を変えることができる． 兄弟が両方とも最適な行動をとった場合，兄がする必要のある質問の数は最大でいくつ？

方針

それぞれの最適な戦略は，弟はできるだけ No と言い続け， 兄は船が存在し得ない範囲を広げて追い込んでいくというもの．

ある行に船が存在しないことを保証するために必要な質問の回数は $\lfloor C/W \rfloor$ である． 左から 1-indexed で $W$ の倍数のマスに対して質問していけばこうなる． これを最後の行に追い込むまで $R-1$ 回やる．

最後の行に追い込んだら，まずは同じように $W$ の倍数で質問していく． 弟は最後の $\lfloor C/W \rfloor$ 番目の質問には Yes と答えざるをえない．

その後は，$C$ が $W$ の倍数ならその右にはマスが存在しないので， 左にある残りの $W-1$ マスを順に埋めていけばいい． 倍数でない場合は，左右どちらに伸びている可能性もあるので， まず左右どちらに伸びているかを弟に問い合わせて， 左右が定まったらそっちの方向を埋めていく．

実装

int solve(int C, int W){
    int ans = C/W-1+W;
    if(C%W==0){
        ans = max(ans, C/W+W-1);
    } else {
        ans = max(ans, C/W+W);
    }
    return ans;
}

int solve(int R, int C, int W){
    int ans = C/W*(R-1) + solve(C,W);
    return ans;
}

signed main(){
    ios_base::sync_with_stdio(0); cin.tie(0);
    int T;
    cin >> T;
    rep(i,T){
        int R,C,W;
        cin >> R >> C >> W;
        int ans = solve(R,C,W);
        printf("Case #%d: %d\n",(int)i+1,ans);
    }
}