AOJ2208 UTPC2010 E: The Melancholy of Thomas Right
解法
行の赤丸の数で降順sortする。全ての列の一つの赤丸で一行を丁度全て使いきったなら正しい。それをすべての行でループする二重ループ。
このGreedyで何故一意に復元できると言えるのかはわからない。
int n, row[10000], col[10000]; bool solve() { sort(row, row+n, greater<int>()); for(int i=0; i<n; i++) { for(int j=0; j<n; j++) { if(col[j] > 0) col[j] --, row[i] --; } if(row[i]!=0) return false; } return true; }