空き地 について、 をその空き地の周囲 マスにある家の数とする。
空き地 に木を一本植えると、その木は周囲にある各家の木の本数に一回ずつ数えられる。したがって、全体の総和はちょうど だけ増える。異なる空き地の寄与は互いに影響しない。
よって問題は、 以上 以下の値 のうちいくつかを選び、その和を 以上にしつつ、選ぶ個数を最小化する問題に置き換えられる。同じ本数の木を植えるなら、得られる総和を最大にするには大きい から選ぶのが最適である。したがって、 の順に必要なだけ選べばよい。
すべての空き地の の総和が より小さい場合、条件を満たすことはできないので -1 を出力する。 の場合は一本も植える必要がないため、答えは である。
各空き地の は周囲の最大 マスを調べれば求められる。 は のいずれかなので、各値の個数を数えるだけでよく、ソートは不要である。計算量は各テストケースについて 、全体では である。グリッドの保存に のメモリを使用する。
Solution written by GPT5.6
