POJ-3692 : Kindergarten

問題概要

二つの完全グラフ(サイズ200以下)の間にいくつか辺がはられたようなグラフがある。最大クリークを求める問題。

解法

元のグラフのcomplementを考えると二部グラフになっていて最大独立集合を求めれば良いことが分かる。なので|最大独立集合|=|V|-|最小点被覆|=|V|-|最大マッチング|を求めれば良い。

2011-2012 Waterloo Local Contest, 24 September, 2011 D : Largest Square

問題概要

01の二次元配列が与えられる(N*N, N<2000)。1を高々L個しか含まないような最大正方形を求める問題。

解法

サイズに関して二分探索+累積和で前処理をかけておくことによりO(N)で判定できる。