ABC112C

https://gyazo.com/26703e70d37462b7f880bcd2126d9014

考えたこと

高さ0の頂点を無視したくなるけど、高さ0の頂点をヒントにしないと確定しないパターンが作れるからダメだな

同じ高さの点が3個あれば、配置によっては確定するな

https://gyazo.com/fc11dd9f3a19cd2f8c5de5d6d876d47d

うーん、同じ高さの点がまったくないこともあり得るよなぁ

一つの観測点が作る制約

自分が頂点である、か、

自分の周囲8マスに1高い頂点がある、か…

と、全マスにたいして、そこに頂点があるなら高さがいくらかという制約が生まれる

二つ目の観測点の制約でほとんどの頂点が不可能になる

100個の観測点について100×100のマスについて更新しても間に合う

実際には2個目から可能な候補は激減するからそれをリストにでも入れてそこだけ更新することもできる

公式解説

「すべての観測点が0ということはない」の証明があった

0の時は制約の形がちがう

不等号制約になる

最初に非0の観測点で位置と高さの対を作っておいて、矛盾したものを消していくスタイル