D - Pair of Balls

・問題URL

https://atcoder.jp/contests/abc216/tasks/abc216_d

・発想

・本番で解けなかったやつ。
・”筒”がいかにもqueueやstackを匂わせている。

・解法

「毎回筒の先頭を全部見て、同じのがあったら消してシフト」みたいなことをするとO(NM)はかかるのでダメ。もう一本筒QUEを作り、M本の筒の先頭にある色iの個数=2ならその色をQUEに入れる。次にQUEから順番に色を取り出してその色があった二本の筒の中身をシフトする。シフトしてできた筒の色を調べ、新たにQUEに入れるなどする。各QUEの要素に対しこれはO(1)。(なぜならどの色も２個しかないから、シフトや新しい先頭の調査は２回ずつしか起こらないため。)QUEの要素数は高々Nなのでこのループ部分はO(N)。答えの判定にO(M)。よって結局入力がボトルネックになりこの問題はO(N+M)で解ける。

・コード

int main(){
 
 int N,M;
 cin>>N>>M;
 vector<queue<ll>>que(M);

 //N色の箱を作る。
 vector<vector<ll>>sento(N);

 rep(i,M){
   ll k;
   cin>>k;
   rep(j,k){
     ll a;
     cin>>a;
     a--;
     que[i].push(a);
   }

   //i番目の筒の先頭にある色の箱に筒の番号を入れる。
   sento[que[i].front()].push_back(i);
 }

 queue<ll>QUE;
 rep(i,N){
   if(sento[i].size()>1){
     //先頭に色iが2色あるなら入れる。
     //この時点で一組もなければ下のwhileはカット
     QUE.push(i);
   }
 }

 //高々N回のループ
 while(!QUE.empty()){
   //消す色
   ll Erase=QUE.front();
   QUE.pop();
   //消す色が先頭にある２本の筒に対して
   for(auto v:sento[Erase]){
     que[v].pop();
     //もし消したあとも空じゃないならシフト
     if(!que[v].empty()){
       sento[que[v].front()].push_back(v);
       //シフトして先頭に来たやつの色の箱に筒の番号を入れる
       //ここでペアがそろえば次に消せるのでQUEに入れる
       if(sento[que[v].front()].size()>1)QUE.push(que[v].front());
     }
   }
 }
 
 bool Q=true;
 //すべての筒が空かどうか
 rep(i,M){
   if(!que[i].empty())Q=false;
 }
 if(Q)cout<<"Yes"<<endl;
 else cout<<"No"<<endl;

}