11月祭プログラミングコンテスト2019 : E. Bridge Battle

これもシンプルな問題設定で良いね。
https://www.hackerrank.com/contests/nf-procon-2019/challenges/bridge-battle

問題

頂点1～Nからなるグラフがあり、初期状態では辺がない。
2人交互に、まだ辺の頂点対を1つ選び、辺を追加する、という処理を繰りかえすゲームを行う。
その際、頂点u-v間に辺を張ると、u*vのコストがかかる。
途中、頂点1とNが連結した時点で終了となり、その時点でコストが少ない方が勝ちである。

Nが与えられたとき、両者が最適手を取ると勝者はどちらか。

解法

基本的には、1-(N-1)の間の頂点のうち、コストが小さい辺をつなぐということを繰り返す。
そうするとただし、全頂点対を使い切ったか、またはコストがN増えても勝てるなら、1-N間をつないでゲームを終了させる。

愚直にシミュレートしてみると、2N回ぐらい辺を張ってみるとコスト差がN以上になり終了するのがわかる。

int N;
int nex[101010];
void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	int turn=0;
	priority_queue<pair<ll,int>> P;
	vector<ll> V;
	for(i=1;i<=N-2;i++) {
		P.push({-1LL*i*(i+1),i});
		nex[i]=i+2;
	}
	ll sum=0;
	while(P.size()) {
		ll sc=-P.top().first;
		int cur=P.top().second;
		P.pop();
		if(nex[cur]<N) {
			P.push({-1LL*cur*nex[cur],cur});
			nex[cur]++;
		}
		
		if(turn==0) {
			if(sum<=-N) return _P("First\n");
			sum+=sc;
		}
		else {
			if(sum>N) return _P("Second\n");
			sum-=sc;
		}
		turn^=1;
		//cout<<turn<<" "<<cur<<" "<<sc<<" "<<sum<<endl;
	}
	if(turn==0) sum+=N;
	else sum-=N;
	
	if(sum>0) {
		cout<<"Second"<<endl;
	}
	else {
		cout<<"First"<<endl;
	}
	
	
}

まとめ

O(N^2)かかるかと思ったらそれ以前に終わってびっくり。