1回仮に割り当てておいて、条件を満たさないものを見つける、2段階ロケット🚀🚀

• Quiz
  • C.Basic Diplomacy
  • https://codeforces.com/contest/1484/problem/C
• AC
  • https://codeforces.com/contest/1484/submission/111858181
• 解説
  • 1度、適当にM日分アサインする
  • 条件を満たさない人（オーバーしてしまう人）がいるとすれば1人で、それをｆ君とする
  • ｆ君しかいない日が上限より多くあるなら、不可能（NOを出力）
  • そうでないなら、割り当て可能（下記コード参照）
• その他
  • 上記解説の考え方が、2段階ロケット🚀🚀に思えて新鮮だった

void solve(){
  ll N,M;
  cin>>N>>M;

  // 超えてはいけないバー
  ll bar=(M+1)/2;

  // M days
  VV G(M);
  rep(i,M){
    ll n;cin>>n;
    while(n--){
      ll a;cin>>a;a--;
      G[i].push_back(a);
    }
  }

  // 仮に割り当てる
  VI A(M);
  rep(i,M)A[i]=G[i][0];

  ll f=-1;
  VI C(N); // カウント
  for(ll a : A){
    C[a]++;
    if(C[a]>bar){
      debug(a, "is over");
      f = a;
      break;
    }
  }

  if(f==-1){
    // 誰もoverしなかったならそのまま出力
    p_yes();
    print_vector(A,1);
    return;
  }

  // f君しかいない場所はいくつあるか
  ll f_only_cnt=0;
  rep(i,M){
    if(G[i].size()==1 && G[i][0]==f)f_only_cnt++;
  }
  if(f_only_cnt>bar){
    p_no();return;
  }

  // 以降、f君しかいない場所はbar以下

  ll f_limit = bar;
  rep(i,M)A[i]=-1; // reset
  // f君しか入れない所には、アサインする
  rep(i,M){
    if(G[i].size()==1 && G[i][0]==f){
      A[i]=f;
      f_limit--;
    }
  }
  rep(i,M){
    if(A[i]!=-1)continue;
    bool f_exist=false;
    for(ll a : G[i]){
      if(a==f)f_exist=true;
    }
    if(f_exist && f_limit>0){
      // fを割り当てる
      A[i]=f;
      f_limit--;
    }
    else{
      // f以外を割り当てる
      for(ll a : G[i]){
        if(a!=f){
          A[i]=a;
          break;
        }
      }
    }
  }
  p_yes();
  print_vector(A,1);
}

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);

    // input
    ll N;cin>>N;
    while(N--)solve();
    
    return 0;
}