- 考えたこと
- 高さ0の頂点を無視したくなるけど、高さ0の頂点をヒントにしないと確定しないパターンが作れるからダメだな
- 同じ高さの点が3個あれば、配置によっては確定するな
- うーん、同じ高さの点がまったくないこともあり得るよなぁ
- 一つの観測点が作る制約
- 自分が頂点である、か、
- 自分の周囲8マスに1高い頂点がある、か…
- と、全マスにたいして、そこに頂点があるなら高さがいくらかという制約が生まれる
- 二つ目の観測点の制約でほとんどの頂点が不可能になる
- 100個の観測点について100×100のマスについて更新しても間に合う
- 実際には2個目から可能な候補は激減するからそれをリストにでも入れてそこだけ更新することもできる
- 公式解説
- 「すべての観測点が0ということはない」の証明があった
- 0の時は制約の形がちがう
- 不等号制約になる
- 最初に非0の観測点で位置と高さの対を作っておいて、矛盾したものを消していくスタイル
