ARC041 B 考察

ARC041 B アメーバ

縦 N マス横 M マスの盤面があって各マスには a[i][j] のアメーバが居る。各アメーバは上下左右に 4 分裂した。入力では分裂後の盤面 b が与えられる。 a を求める。

2 行目から N - 1 行目まで 2 列目から M - 1 列目まで走査する。各マスについて 4 方向のうち最も小さい値を選ぶ。それが分裂前にそのマスに居たアメーバの数になる。既に確定したアメーバ分を取り除いておく。制約は N <= 500 M <= 500 なので 4 方向をすべて走査しても間に合う。

解説を読むと上から走査していれば 4 方向を走査しなくても良かったようだ。

https://atcoder.jp/contests/arc041/submissions/15353600

リングフィットアドベンチャー 34 日目 レベル 72 ワールド 8 。

子ども用の電動歯ブラシの替えブラシを買った。届いたら試す。