kmjp's blog

競技プログラミング参加記です

JOIG 2024/2025 本選 : D - 最悪の記者 5 (Worst Reporter 5)

こちらは割とすんなり。
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;
}

まとめ

解法は思いついても実装がちょっとめんどかった。