kmjp's blog

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

TopCoder SRM 700 Div1 Easy FindingFriend

朝回なので不参加。
https://community.topcoder.com/stat?c=problem_statement&pm=14166

問題

R*N人が参加してSRMを行った。
各人は1~(R*N)位の順位が付けられ、タイはいなかった。
参加者はN個の部屋にR人ずつが割り当てられており、各部屋iのleaderの順位L[i]が与えられている。
F番の人が参加していた可能性のある部屋はいくつか。

解法

L[i]にFが含まれていればその部屋は確定。
L[i]>Fの部屋は関係ないので、以下そのような部屋は除いて考える。

L[i]の小さい順にソートし、F番の人が各j番の部屋で参加していたかどうかを総当たりしよう。
各部屋は(L[i]+1)以降の順位の人が最大(R-1)人存在しうる。
これとj番目の部屋の人で合計F人分を超えるなら条件を満たせる。

以下をそれぞれ考える。

  • j番以外の部屋で順位未確定の人の総数
  • j番の部屋で順位未確定の人の総数

部屋をL[i]の小さい順に見ていくとき、L[i]-L[i-1]番の順位の人は、i番未満の部屋で充当しなければならない。
出来るだけ前者から充当し、どうしても足りないときだけ後者を割り当てよう。
最終的に後者の人が1人でも残っているなら、その人をF番にすることができる。

class FindingFriend {
	public:
	int find(int roomSize, vector <int> L, int friendPlace) {
		sort(L.begin(),L.end());
		FORR(r,L) if(r==friendPlace) return 1;
		while(L.size() && L.back()>friendPlace) L.pop_back();
		int N=L.size();
		
		int i,j;
		int ret=0;
		FOR(i,N) {
			ll a=0,b=0;
			ll pre=0;
			FOR(j,N) {
				ll dif=L[j]-pre-1;
				ll m=min(a,dif);
				a-=m;
				dif-=m;
				b-=dif;
				if(a<0 || b<0) break;
				
				if(i==j) b+=roomSize-1;
				else a+=roomSize-1;
				pre=L[j];
			}
			ll num=friendPlace-pre;
			if(b==0) continue;
			if(num<=a+b) ret++;
		}
		return ret;
		
	}
}

まとめ

WebのMatch Resultがすぐに更新されればこんな面倒は方法で友人を探さなくても良いのだけども。