Hatena::Grouptopcoder

SRM diary(Sigmar)

SigmarのTopcoder SRM参加記録など雑記です。
社会人になってから競技プログラミングを始めました。どこまで行けるか分かりませんが合間を見つけてアルゴリズムの勉強をしています。

2011-12-11SRM526 Div1(Practice)

SRM526 Div1 500 PrimeCompositeGame

| 14:27 | SRM526 Div1 500 PrimeCompositeGame - SRM diary(Sigmar) を含むブックマーク はてなブックマーク - SRM526 Div1 500 PrimeCompositeGame - SRM diary(Sigmar) SRM526 Div1 500 PrimeCompositeGame - SRM diary(Sigmar) のブックマークコメント

Problem Statement

解答方針

大まじめにDPなどすれば当然間に合わないということで、何か法則があるんだろうということはすぐ想定できる

問題は何の法則があるのか分からないということだが・・


とりあえず自分が勝てる条件と相手が勝てる条件を考える

  • 5以上の任意の素数は1引くと合成数ということで、5以上のときにそのターンで相手が負けることはあり得ない。逆に3以下になると合成数がないので必ず相手が負ける
  • 相手が勝てる条件は・・・何か難しそうなので後回しにしよう(←実は難しくなかった)

自分が勝てる2や3から逆順にシミュレートできないか。

色々考えたけどよく分からない。うーむ。


もう一回相手が勝てる条件を考える。

少なくとも合成数がK連続するときに相手が勝てるよなぁ・・

ってそれが全てじゃないのか。相手が勝てる条件は、自分の番で数字nのときにn-1からn-kまで全部合成数の場合だけだ

ってことは、、、合成数がK+1個連続するか、初期値Nの下が合成数がK個連続していれば自分の負け。それ以外は勝ち。

シミュレーションは書くだけっぽいな・・


書いた。

何か意外とこまごました条件があって面倒くさかった

一応一発で通った。


ソースコード

(12/22追記)

Editorial見たら普通にDPで解ける問題だった

multisetとか使えばlog nで遷移先候補の更新と遷移先の判定ができるですね。。。

しかしmultisetとか意外と扱いづらく書くのは結構難しい気がする

・自己解法(Greedy)

vector <int> gvn;

vector <int> cpn(int n) {
	vector <int> vn(max(2, n+1), 1);

	vn[0]=vn[1]=0;
	for(int i=2; i*i<=n; i++) {
		if(!vn[i]) continue;
		for(int j=i*i; j<=n; j+=i) vn[j]=0;
	}
	
	return vn;
}

class PrimeCompositeGame {
public:
	int maxlose;

	int simulatew(int N, int K) {
		int res=0;
		while(1) {
			for(int i=max(2, N-K); i<N; i++) {
				if(gvn[i]) {
					N=i;
					res++;
					break;
				}
			}
			if(N<=3) break;
			N--;
			res++;
		}
		return res;
	}

	int simulatel(int N, int K) {
		int res=0;
		while(1) {
			for(int i=N-1; i>=N-K; i--) {
				if(i<=maxlose) return res;
				if(gvn[i]) {
					N=i;
					res--;
					break;
				}
			}
			for(int i=max(maxlose, N-K); i<N; i++) {
				if(!gvn[i]) {
					N=i;
					res--;
					break;
				}
			}
		}
		return res;
	}

	int theOutcome(int N, int K) {
		int res;
		gvn=cpn(500001);

		if(N<=2) return 0;
		if(N==3) return 1;

		int cnt=0;
		maxlose=0;
		for(int i=1; i<=N; i++) {
			if(cnt>=K && (!gvn[i] || i==N)) maxlose=i;
			if(!gvn[i]) cnt++;
			else cnt=0;
		}

		if(maxlose==0) res=simulatew(N, K);
		else res=simulatel(N, K);

		return res;
	}
};

DP解法

const int INF=1000000000;
vector <int> gvn;
int dp[2][500000];
multiset <int> cand[2];

vector <int> cpn(int n) {
	vector <int> vn(max(2, n+1), 1);

	vn[0]=vn[1]=0;
	for(int i=2; i*i<=n; i++) {
		if(!vn[i]) continue;
		for(int j=i*i; j<=n; j+=i) vn[j]=0;
	}
	
	return vn;
}

class PrimeCompositeGame {
public:
	int K;

	void updatedp(int &dpv, multiset <int> &candt) {
		if(candt.empty()) dpv=0;
		else {
			dpv=*candt.begin();
			if(dpv>INF/2) dpv--;
			else dpv++;
			dpv=INF-dpv;
		}
	}

	void updatecand(multiset <int> &candt, int idx, int doctor, int dpt[]) {
		if(!(gvn[idx]^doctor)) {
			candt.insert(dpt[idx]);
		}
		if(idx-K>=2 && !(gvn[idx-K]^doctor)) {
			multiset <int>::iterator msi=candt.find(dpt[idx-K]);
			candt.erase(msi);
		}
	}

	int theOutcome(int N, int K_) {
		int res;
		K=K_;

		gvn=cpn(N+1);

		cand[0].clear(); cand[1].clear();
		memset(dp, 0, sizeof(dp));
		dp[0][1]=dp[1][1]=0;
		for(int i=2; i<=N; i++) {
			for(int j=0; j<2; j++) updatedp(dp[j][i], cand[j]);
			for(int j=0; j<2; j++) updatecand(cand[1-j], i, j, dp[j]);
		}

		res=dp[0][N];
		if(res>INF/2) res-=INF;
		res=-res;
		return res;
	}
};
トラックバック - http://topcoder.g.hatena.ne.jp/jackpersel/20111211