No.511

並列二分探索を使う.

$t$ ターン終わったときに $i$ 列目が $h$ 以上になるかどうかを調べる. これはいもす法を使えば $O(n+w)$ で調べることができる.

そこでまずは $t = n/2$ で $h$ を超える列と超えない列に分ける. 超える列については $t = n/4$ を調べ, 超えない列については $t = 3n/4$ を調べる.

以下これを繰り返して各列が初めて $h$ を超えるターンを求める. 並列二分探索なので $O((n+w)\log n)$ で求められる.

あとはターンの偶奇を見れば両人の得点がわかる.