Rectangular

原案: chokudai
解答: chokudai, hos
解説: chokudai
スタンプを使って、4*4の絵を完成させる。
 スタンプは何色でも塗ることが可能。
 スタンプをはみ出させて押すことも可能。
 最低何回押すことで絵を完成させることができ
るか？

マスの数は、4*4の16マス
 色の種類は、RGBWの４種類
 4^16の状態数


このまま幅優先探索等を行うと、状態数が多
すぎて探索出来ない。
４色をそのまま保持するのではなく、「正しい
色」「正しくない色」の２色に分けてしまう
 これにより、2^16に減らすことが可能！

与えられるスタンプは最大16個
 これをx,y共に-3～+3に動かすと、押し方は
16 * 7 * 7 = 784通り
 これらに対して、16回毎回処理してしまうと、
2^16 * 784 * 16 * 3となり、間に合わない。

そもそも、4*4の三角形を長方形で塗りつぶ
す方法は、(5C2)^2 = 100通りしかない。
 毎回スタンプを選ぶのではなく、100通りの押
し方のうち、どの押し方が可能かを覚えておけ
ば、計算量を減らせる。

毎回16マスに対して操作をするのは大変
 Bit演算を使って、計算を省略しよう！
 1bitに１マスを対応させる！


どの長方形にどの色を塗ると、
どの部分が正しい色になるかのbit情報
 どの部分が違う色になってしまうかのbit情報


をメモっていけば、十分早く終わる！
First submission: 29min (rng_58)
 First accepted: 31min (rng_58)
 Number of submissions: 45
 Number of accepted: 13


Download Report