この分野に関しては具体的な問題はまだ遭遇量が少ないため、個別に知見を置く。
置ける最大サイズと要求されるサイズの差
構築問題では、最大で置けるサイズよりも、実際構築要求されるサイズがかなり小さい場合がある。
この時、基本的にグリッドでは、一面をまず1色に塗り、そこにぽつぽつ別の色を塗っていくというテクニックがある。
例題を見たほうが早い。
ARC093 - D(500)
この問題は、まさに上記のテクニックが該当する。
要求される独立成分はたかだか1000個、Wだけを考えれば500個。
100^2の左半分をBでまず塗って、そこでWをぽつぽつ落とすことを考えてみる。
100 * 100 / 2 = 5000個のグリッドの中で、最大限重複しないWの独立集合を作るには
要求される独立成分はたかだか1000個、Wだけを考えれば500個。
100^2の左半分をBでまず塗って、そこでWをぽつぽつ落とすことを考えてみる。
100 * 100 / 2 = 5000個のグリッドの中で、最大限重複しないWの独立集合を作るには
#####
#.#.#
#####
#.#.#
#####
のようにする必要がある。一つの . あたりには多く見積もっても、(他との共有を無視して)周りの8個必要であるが、たかだかAは500個しかないので、たかだか4000個のグリッドで済みそうだとわかる。(これは実際よりもかなり多く予想してるはず)
よって、上記のテクニックそのまま使えばよい。
上はAについてのやるべきことだが、Bも同様にもう半分のグリッドで似たようなことやればよい。
よって、上記のテクニックそのまま使えばよい。
上はAについてのやるべきことだが、Bも同様にもう半分のグリッドで似たようなことやればよい。
