問題概要 T字型のペントミノをH*W(H,W 解法 2行覚えておくビットDPでもいけるけど復元がとても面倒。普通に探索する。分枝限定法で枝刈りできる。 また、この問題は最大独立集合だとみなすこともできる(ノード数9*9*4)。いつか最大独立集合ソルバができたら…

問題概要 H*W(H,W 解法 同時に置くことができないふたつのマスの間に辺をはると二部グラフになっている。もとめたいものは最大独立集合なので、|V|-|最小点被覆|=|V|-|最大マッチング|で求められる。ただしグラフがそれなりに大きいので最大マッチングはhopc…

問題概要 ある正整数A,B,Cがあり、(A-1)*(B-2)*(C-2)の値が与えられる。A*B*Cの値として考えられる最小値と最大値を求める問題。 解法 全探索する。

結果。 順位としては悪くなくて、レートも上がったんだけどCは解けなきゃいけない気がする。 Aは割とやるだけ、Bは二部マッチングにはすぐ気づけたけどhopcroft書いたことなかったのでちょっと手間取った。Cは2行持ったビットDPか探索だと思ったけど、復元が…