1020

むずかった。正方形だけで構成されたペントミノの問題で、全解を調べなくても良いから解があるかどうかだけ調べろっていう話。隙間が無いことを考慮して

1. できるだけ上の点
2. できるだけ左の点

の順で正方形の大きさを小さくして配置していく。UNIX端末室のペントミノ解探索スクリーンセーバーを思い出してその通りに作ってみた。最初はずらしながら作ってて、もちろんTLEになった。二回目はACになった方法の前段階で、ここにこの大きさの正方形を置いたけどダメだったっていう情報を保存して、その情報を頼りに枝刈り。でもよく考えたら前方の配置によって置いても大丈夫かどうかは変化してしまうためこの方法は無理。当然WA。そんで同じ種類の正方形を連続して同じ場所に配置していたので、それを改善したらある程度速くなってAC。でも400msとかかかってるからもう少し良い方法を考えたい。