こちらは割とすんなり。
https://atcoder.jp/contests/joig2025-open/tasks/joig2025_d
問題
N人の選手でマラソン大会を行っている。
開始時点で、N人は1~N位のいずれかであり、互いに異なる順位となっていた。
その後、M回追い抜きが発生した。
追い抜きが生じた2名の情報が与えられるが、どちらが追い抜いた側/追い抜かれた側かは与えられない。
最終的な順位として、あり得るものがあれば、辞書順最小のものを答えよ。
解法
前後にいる人の番号を、リスト構造で管理しよう。
初期状態では、N人は互いに連結しないN個のリストを持つ。
追い抜きが発生したということは、その時点でその2名は隣同士にいることになる。
その2名がすでにリストで隣接してない場合、新たに両者を連結する。
もし途中、隣の順位の人が3名いる状況が発生したら、条件を満たす並びは存在しない。
最終的に、いくつかのリストが残る。
各リストは、端点のうちどちらが順位が低い/高い方か確定してないので、そこは辞書順が小さくなるように確定させよう。
また、各リストの並び順は任意なので、辞書順最小にするために先頭の人の番号が小さい順に並べよう。
int N,M; int id[505050]; int nex1[505050],nex2[505050]; int vis[505050]; vector<vector<int>> ret; void solve() { int i,j,k,l,r,x,y; string s; cin>>N>>M; FOR(i,M) { cin>>x>>y; if(nex1[x]==y||nex2[x]==y) { hoge: int px=nex1[x]+nex2[x]-y; int py=nex1[y]+nex2[y]-x; if(nex1[x]==y) nex2[x]=py; else nex1[x]=py; if(nex1[y]==x) nex2[y]=px; else nex1[y]=px; if(nex1[py]==y) nex1[py]=x; else nex2[py]=x; if(nex1[px]==x) nex1[px]=y; else nex2[px]=y; } else if((nex1[x]==0||nex2[x]==0)&&(nex1[y]==0||nex2[y]==0)) { if(nex1[x]==0) nex1[x]=y; else nex2[x]=y; if(nex1[y]==0) nex1[y]=x; else nex2[y]=x; goto hoge; } else { cout<<"No"<<endl; return; } } for(i=1;i<=N;i++) if(vis[i]==0&&(nex1[i]==0||nex2[i]==0)) { vector<int> p={i}; vis[i]=1; if(nex1[i]==0&&nex2[i]==0) { ret.push_back(p); } else { p.push_back(nex1[i]+nex2[i]); vis[p.back()]=1; while(1) { x=nex1[p.back()]; if(x==p[p.size()-2]) x=nex2[p.back()]; if(x==0) break; vis[x]=1; p.push_back(x); } if(p[0]>p.back()) reverse(ALL(p)); ret.push_back(p); } } for(i=1;i<=N;i++) if(vis[i]==0) { cout<<"No"<<endl; return; } sort(ALL(ret)); cout<<"Yes"<<endl; FORR(a,ret) FORR(p,a) cout<<p<<endl; }
まとめ
解法は思いついても実装がちょっとめんどかった。