kmjp's blog

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

AtCoder ABC #218 : G - Game on Tree 2

こちらはそこまで難しくなかった。
https://atcoder.jp/contests/abc218/tasks/abc218_g

問題

根付き木が与えられる。
各点には、スコアが設定されている。

この木を使い、2人でゲームを行う。
初期状態でコマが根頂点においてある。
交互に、現在の頂点に子頂点があれば、そのいずれかを選択してコマを動かす、という作業を繰り返す。
コマが葉に到達したら終了であり、そのゲームの最終スコアは、経由した頂点のスコアの中央値とする。

先手はスコアを最大化、後手は最小化するとき、最終スコアはどうなるか。

解法

まず、各葉において、そこに到達したときのスコアを求めよう。
これは中央値を求める定番テクとして、DFSを行いながら経由した点において以下のいずれかを行えばよい。

  • 上半分と下半分をそれぞれ保持するmultisetを持つ
  • 各頂点のスコアを座標圧縮しておき、BITであるスコア以下の頂点数を高速に計算できるようにして二分探索

あとは、min-max法の要領で最適値を求める。

int N;
int A[202020];
vector<int> As;
vector<int> E[202020];

template<class V, int ME> class BIT {
public:
	V bit[1<<ME],val[1<<ME];
	V operator()(int e) {if(e<0) return 0;V s=0;e++;while(e) s+=bit[e-1],e-=e&-e; return s;}
	void add(int e,V v) { val[e++]+=v; while(e<=1<<ME) bit[e-1]+=v,e+=e&-e;}
	void set(int e,V v) { add(e,v-val[e]);}
	int lower_bound(V val) {
		V tv=0; int i,ent=0;
		for(i=ME-1;i>=0;i--) if(tv+bit[ent+(1<<i)-1]<val) tv+=bit[ent+(1<<i)-1],ent+=(1<<i);
		return ent;
	}
};
BIT<int,20> bit;

ll dfs(int cur,int pre,int turn) {
	int x=lower_bound(ALL(As),A[cur])-As.begin();
	bit.add(x,1);
	
	ll ret;
	if(cur&&E[cur].size()==1) {
		int N=bit(1<<19);
		
		int a=bit.lower_bound((N+1)/2);
		int b=bit.lower_bound((N+2)/2);
		ret=As[a]+As[b];
	}
	else {
		if(turn==0) {
			ret=-1LL<<60;
			FORR(e,E[cur]) if(e!=pre) ret=max(ret,dfs(e,cur,1));
		}
		else {
			ret=1LL<<60;
			FORR(e,E[cur]) if(e!=pre) ret=min(ret,dfs(e,cur,0));
		}
	}
	
	bit.add(x,-1);
	return ret;
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	FOR(i,N) {
		cin>>A[i];
		A[i]/=2;
		As.push_back(A[i]);
	}
	sort(ALL(As));
	As.erase(unique(ALL(As)),As.end());
	
	FOR(i,N-1) {
		cin>>x>>y;
		E[x-1].push_back(y-1);
		E[y-1].push_back(x-1);
	}
	
	cout<<dfs(0,0,0)<<endl;
	
}

まとめ

中央値と聞いて二分探索したくなったのは反省。