Google Code Jam 2020 Round 1A : C. Square Dance

しょうもないミスでタイムロスが痛い。
https://codingcompetitions.withgoogle.com/codejam/round/000000000019fd74/00000000002b1355

問題

ダンス競技会が行われている。
グリッド上の各マスに1人ずつ参加者がおり、各人のスキル値が与えられる。

今i回目の演技を行ったとする。
各人の隣接競技者とは、上下左右方向それぞれの方向にいる最寄りの選手のこととする。
もし隣接競技者が1人以上して、それらのスキルの平均が自分のスキルより高い場合、その競技者は次の演技の前に敗退してグリッドから取り除かれる。

演技のパフォーマンスとは、その時点で残っている競技者のスキルの総和とする。
取り除く人がいなくなるまで演技を繰り返したとき、パフォーマンスの総和を求めよ。

解法

毎回愚直に全員のスキル判定を行うと当然TLEする。
1人が取り除かれる影響が次の演技に現れるのは、その上下左右4人しかいないことを考え、その4人だけ次の演技で敗退するかどうかを判定できるようなデータ構造を考えよう。

そのため、各人に対し、上下左右方向にリンクリストを張る。
一人人が抜ける場合、上下方向と左右方向それぞれで自分を削除する（自分の上と下、左と右の人を直接接続）するようにしよう。

あとは、これを用いて演技毎に以下を行う。

• 初回は全員、2回目以降は隣接者が変更した人について、演技で取り除かれるか判定する。
• 取り除くと判定した人を取り除き、その分グリッド上のスキルの総和を減算する。また、人を取り除いた影響でリンクリストに変更が生じた人を覚えておく。
• リンクリストに変更が生じた人について、再度スキルの判定を行い、次の演技で取り除かれるか判定する。

int H,W;

struct node {
	int L,R;
	int U,D;
	int val;
	int alive;
};
vector<node> V[101010];
vector<pair<int,int>> cand,cand2;

int ng(int y,int x) {
	int num=1;
	int sum=V[y][x].val;
	if(V[y][x].L>=0) num++,sum+=V[y][V[y][x].L].val;
	if(V[y][x].R<W) num++,sum+=V[y][V[y][x].R].val;
	if(V[y][x].U>=0) num++,sum+=V[V[y][x].U][x].val;
	if(V[y][x].D<H) num++,sum+=V[V[y][x].D][x].val;
	return V[y][x].val*num<sum;
}

void solve(int _loop) {
	int f,i,j,k,l,x,y;
	
	cin>>H>>W;
	ll sum=0,ret=0;
	FOR(y,H) {
		V[y].resize(W);
		FOR(x,W) {
			cin>>V[y][x].val;
			V[y][x].L=x-1;
			V[y][x].R=x+1;
			V[y][x].U=y-1;
			V[y][x].D=y+1;
			V[y][x].alive=1;
			sum+=V[y][x].val;
		}
	}
	
	FOR(y,H) FOR(x,W) {
		if(ng(y,x)) cand.push_back({y,x});
	}
	ret=sum;
	while(cand.size()) {
		cand2.clear();
		FORR(c,cand) {
			x=c.second;
			y=c.first;
			sum-=V[y][x].val;
			V[y][x].alive=0;
			if(V[y][x].L>=0) {
				cand2.push_back({y,V[y][x].L});
				V[y][V[y][x].L].R=V[y][x].R;
			}
			if(V[y][x].R<W) {
				cand2.push_back({y,V[y][x].R});
				V[y][V[y][x].R].L=V[y][x].L;
			}
			if(V[y][x].U>=0) {
				cand2.push_back({V[y][x].U,x});
				V[V[y][x].U][x].D=V[y][x].D;
			}
			if(V[y][x].D<H) {
				cand2.push_back({V[y][x].D,x});
				V[V[y][x].D][x].U=V[y][x].U;
			}
		}
		cand.clear();
		sort(ALL(cand2));
		cand2.erase(unique(ALL(cand2)),cand2.end());
		FORR(c,cand2) if(V[c.first][c.second].alive && ng(c.first,c.second)) cand.push_back(c);
		ret+=sum;
	}
	
	
	_P("Case #%d: %lld\n",_loop,ret);
}

まとめ

この1Aは、予選のEより簡単だったね。Interactiveもないし…。