Hatena::Grouptopcoder

SRM diary(Sigmar)

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

2011-12-11SRM526 Div1(Practice)

SRM526 Div1 250 DucksAlignment

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

Problem Statement

解答方針

何かえらく実装が重いような・・・

ある列かある行に寄せる必要があるので全探索する

後は歯抜けになったところを適当に詰める必要がある

これは本当に適当に詰めればいい

よほど変な実装をしなければ同じ解になるはず・・である


ソースコード

自分のポリシー的には絶対にやってはいけないレベルの冗長なコードを書いてしまった

少なくとも行と列は回転などを使って同じコードを使いまわすべきである

class DucksAlignment {
public:
	int minimumTime(vector <string> grid) {
		int res;
		int h=grid.size(), w=grid[0].size();

		int col[52]={0}, row[52]={0};
		int cnt=0;
		for(int i=0; i<h; i++) {
			for(int j=0; j<w; j++) {
				if(grid[i][j]=='o') {
					row[i]=1; col[j]=1;
					cnt++;
				}
			}
		}

		int rinc=1000000000;
		for(int i=0; i+cnt<=h; i++) {
			int trow[52];
			memcpy(trow, row, sizeof(trow));
			int tinc=0;
			for(int j=0; j<i; j++) {
				if(row[j]==0) continue;
				for(int k=i; k<i+cnt; k++) {
					if(trow[k]==0) {
						trow[k]=1;
						tinc+=abs(k-j);
						break;
					}
				}
			}
			for(int j=i+cnt; j<h; j++) {
				if(row[j]==0) continue;
				for(int k=i; k<i+cnt; k++) {
					if(trow[k]==0) {
						trow[k]=1;
						tinc+=abs(k-j);
						break;
					}
				}
			}
			rinc=min(rinc, tinc);
		}

		int cinc=1000000000;
		for(int i=0; i+cnt<=w; i++) {
			int tcol[52];
			memcpy(tcol, col, sizeof(tcol));
			int tinc=0;
			for(int j=0; j<i; j++) {
				if(col[j]==0) continue;
				for(int k=i; k<i+cnt; k++) {
					if(tcol[k]==0) {
						tcol[k]=1;
						tinc+=abs(k-j);
						break;
					}
				}
			}
			for(int j=i+cnt; j<w; j++) {
				if(col[j]==0) continue;
				for(int k=i; k<i+cnt; k++) {
					if(tcol[k]==0) {
						tcol[k]=1;
						tinc+=abs(k-j);
						break;
					}
				}
			}
			cinc=min(cinc, tinc);
		}

		res=1000000000;
		for(int i=0; i<w; i++) {
			int tres=0;
			for(int j=0; j<h; j++) {
				for(int k=0; k<w; k++) {
					if(grid[j][k]=='o') tres+=abs(i-k);
				}
			}
			res=min(res, tres+rinc);
		}

		for(int i=0; i<h; i++) {
			int tres=0;
			for(int j=0; j<h; j++) {
				for(int k=0; k<w; k++) {
					if(grid[j][k]=='o') tres+=abs(i-j);
				}
			}
			res=min(res, tres+cinc);
		}

		return res;
	}
};

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