きままにものづくり

日々の気付いたことなんかを書いてます。

SRM638Div1Easy

問題

サイズNの三次元の空間を考える。XY平面、YZ平面、ZX平面での射影が与えられる。XY平面への射影は、Z方向から光を当てた時にできる影のこととする。サイズ1のオブジェクトが6近傍で接続されていてかつ、射影の結果に矛盾がない場合はPossibleを返し、それ以外の時はImpossibleを返す。

解法

オブジェクトの配置方法にはいくつか候補があるため、射影の結果から一意に求めることはできない。はじめに、6近傍の接続を満たす配置方法を探索し、その結果が射影と矛盾しないかを調べる。

計算量

 O(N^6)

コード

広告を非表示にする