https://atcoder.jp/contests/abc129/tasks/abc129_d
水平方向、垂直方向にそれぞれ見て行った時に、’#’, ‘.‘の連続数を並べた数列を作る。
#..#..
.....#
....#.
#.#...
であったら
[
[1, 2, 1, 2],
[5, 1],
[4, 1, 1],
[1, 1, 1, 3],
]
さらにこれの累積和をとると、
[
[1, 3, 4, 6],
[5, 6],
[4, 5, 6],
[1, 2, 3, 6],
]
となり、(3,4)に置いた光が横方向にどれくらい届くか調べたかったら、
(3,4)が ‘.’ であるかを調べる- 3行目の累積和
[4, 5, 6]を見て、4番目を超えている場所のインデックスを探す(この場合は1番目) - 累積和を取る前の
[4, 1, 1]の対応する場所を見れば、横方向に連続している白マスがカウントできる。
垂直方向も同様にカウントできる。(横方向の連続数)+(縦方向の連続数)-1 を白マスで計算してmaxを取れば良い。