11月祭プログラミングコンテスト2019 : C. Janken Festival

駒場祭でTSG Liveをやってる一方、11月祭でもコンテスト。
https://www.hackerrank.com/contests/nf-procon-2019/challenges/janken-festival

問題

N人の人がおり、各人がじゃんけんで出す手は固定されている。
ここでM回の大会が行われる。
各大会では、区間[L,R]の範囲の人が総当たりで試合をする。

全試合終了後、各人の勝ち・負け・あいこの回数を求めよ。

解法

平面走査の要領で、人を端から見ていく。
まず、累積和で区間における各じゃんけんの手数を求められるようにしておく。

ある人iを走査するとき、区間が[i,j]の大会の処理を行う。
この時、大会の参加者として、[i,j]のうち各手の人の数を加算する。
その後、手数の総和から参加者iの分を引く。これは参加者iが何大会に含まれているかを考えれば、その分を引けばよい。
そうすると、自分の番号以降で、大会で当たる各手数の総和がわかる。

int N,M;
int H[101010];
int S[101010][3];
vector<int> add[101010][2];
int del[101010][2];
ll num[3];
ll W[101010],L[101010],D[103030];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>M;
	FOR(i,N) {
		cin>>H[i];
		FOR(j,3) S[i+1][j]=S[i][j]+(H[i]==j);
	}
	FOR(i,M) {
		cin>>x>>y;
		add[x-1][0].push_back(y);
		del[y][0]++;
		add[y][1].push_back(x-1);
		del[x-1][1]++;
	}
	
	ll valid=0;
	FOR(i,N) {
		valid-=del[i][0];
		FORR(a,add[i][0]) {
			valid++;
			FOR(j,3) num[j]+=S[a][j]-S[i][j];
		}
		num[H[i]]-=valid;
		W[i]+=num[(H[i]+1)%3];
		L[i]+=num[(H[i]+2)%3];
		D[i]+=num[(H[i]+3)%3];
	}
	ZERO(num);
	valid=0;
	for(i=N-1;i>=0;i--) {
		FORR(a,add[i+1][1]) {
			valid++;
			FOR(j,3) num[j]+=S[i+1][j]-S[a][j];
		}
		num[H[i]]-=valid;
		W[i]+=num[(H[i]+1)%3];
		L[i]+=num[(H[i]+2)%3];
		D[i]+=num[(H[i]+3)%3];
		valid-=del[i][1];
	}
	
	FOR(i,N) cout<<W[i]<<" "<<L[i]<<" "<<D[i]<<endl;
}

まとめ

NFってコンテストの開催者のサークル名か何かでしょうか…？