CodeTON Round 5 : D. Tenzing and His Animal Friends

これもいまいちの出来だった回だな…。
https://codeforces.com/contest/1842/problem/D

問題

プレイヤー1名とそれ以外にN人の人がいる。
うち2人のペアに対し、何時間まで一緒に遊べるかという上限が与えられる。

プレイヤーがN人のうち何人かと遊ぶことを何度か行う。
その際、1番の人は常に一緒に遊び、N番の人とは遊ばない。

プレイヤーが他人と遊ぶ時間を最大化したいとき、遊び方の組み合わせを答えよ。

解法

Worshall-Floyedの要領で、2人が一緒に遊べる時間の最小値を求める。
結果的に1番の人と一緒に遊べる時間が求まるので、それが長い順に貪欲に遊ぶ人を追加していくとよい。

int N,M;
ll E[101][101];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>M;
	FOR(i,101) FOR(j,101) E[i][j]=1LL<<60;
	FOR(i,101) E[i][i]=0;
	FOR(i,M) {
		cin>>x>>y;
		x--,y--;
		cin>>E[x][y];
		E[y][x]=E[x][y];
	}
	FOR(k,N) FOR(x,N) FOR(y,N) E[x][y]=min(E[x][y],E[x][k]+E[k][y]);
	if(E[0][N-1]==1LL<<60) {
		cout<<"inf"<<endl;
		return;
	}
	vector<ll> V;
	FOR(i,N) if(E[0][i]<=E[0][N-1]) V.push_back(E[0][i]);
	sort(ALL(V));
	V.erase(unique(ALL(V)),V.end());
	cout<<E[0][N-1]<<" "<<V.size()-1<<endl;
	FOR(i,V.size()-1) {
		ll a=V[i];
		ll b=V[i+1];
		FOR(j,N) cout<<(E[0][j]<=a);
		cout<<" "<<b-a<<endl;
	}
}

まとめ

なんか問題設定が不自然で、素直に受け入れにくい題材だな…。