読者です 読者をやめる 読者になる 読者になる

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;
}