Hatena::Grouptopcoder

SRM diary(Sigmar)

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

2011-06-26TCO2011 Round2

  • 250:230.68, 500:203.23, score:433.91, rank:82, rating:2155(+101)
  • 予想外に500が解けて随分うまくいった。

TCO2011 Round2 250 GuessTheNumberGame

| 13:30 | TCO2011 Round2 250 GuessTheNumberGame - SRM diary(Sigmar) を含むブックマーク はてなブックマーク - TCO2011 Round2 250 GuessTheNumberGame - SRM diary(Sigmar) TCO2011 Round2 250 GuessTheNumberGame - SRM diary(Sigmar) のブックマークコメント

Problem Statement

コーディングフェーズ

何これ むずい

いやしかし落ち着け。Easyからそんなに難しい問題が出るはずがない。

よく考えると、合成数がYだと必ずその因数もYになるはずだ

ということは、素数だけ考えればOKか!!

いや、違う

2がYでも4や8がYとは限らない

素数のべき乗を考えないといけない

まずエラトステネスの篩でnまでの素数を列挙して

各素数について、n以下で最大何乗までいけるか計算する

そしてその指数+1を解に掛けていけば、答えが出る

書いた

サンプル合った

提出

サンプルが非常に強固だから問題なさそう


ソースコード

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;
}

const int MOD= 1000000007;

class GuessTheNumberGame {
public:
	int possibleClues(int n) {
		int res=1;

		vector <int> vn=cpn(n);
		for(int i=2; i<=n; i++) {
			if(vn[i]) {
				ll v=i;
				while(v<=n) {
					v*=i;
					if(v>n) break;
					vn[i]++;
				}
				res=(ll)res*(vn[i]+1)%MOD;
			}
		}

		return res;
	}
};

TCO2011 Round2 500 STable

| 13:30 | TCO2011 Round2 500 STable - SRM diary(Sigmar) を含むブックマーク はてなブックマーク - TCO2011 Round2 500 STable - SRM diary(Sigmar) TCO2011 Round2 500 STable - SRM diary(Sigmar) のブックマークコメント

Problem Statement

コーディングフェーズ

これまたむずい

各セルの文字列長は簡単に計算できるので計算するとして

各セルについて、上と左を比較したときにどちらが辞書順で小さいか判定できれば解ける気がする

うーん・・・・

・・・

・・・

分からん

普通に上のセルと左のセルを1文字ずつ比較してみるか

k文字目が最終的に(i,0)か(0,j)のどのセルに行き着くのかは、各セルの前半と後半が上からきたのか左から来たのか記憶しておけばすぐ求まる

あとは、自明な枝刈りとして、k文字目が同じセルから由来しているのであれば、その文字数分飛ばす

頑張って書いてみた

おおー意外と一瞬で解答出た!!!枝刈りだけでいけるとは。

サンプル強そうだし問題なさそうだな・・・

提出


ソースコード

多くの人はDP的に解いていましたが全く別解法と思われます

class STable {
public:
	//上もしくは左へ進む
	void update(vector <ll> &u, ll len[32][32], int up[32][32]) {
		if(up[u[0]][u[1]]) {
			if(u[2]>=len[u[0]-1][u[1]]) {
				u[2]-=len[u[0]-1][u[1]];
				u[1]--;
			} else u[0]--;
		} else {
			if(u[2]>=len[u[0]][u[1]-1]) {
				u[2]-=len[u[0]][u[1]-1];
				u[0]--;
			} else u[1]--;
		}
	}

	string getString(string s, string t, long long pos) {
		string res;
		int N=s.size(), M=t.size();

		ll len[32][32];
		len[0][0]=0;
		for(int i=1; i<=30; i++) len[i][0]=len[0][i]=1;
		for(int i=1; i<=30; i++) {
			for(int j=1; j<=30; j++) {
				len[i][j]=len[i-1][j]+len[i][j-1];
			}
		}

		vector <string> cc(N+1, string(M+1, ' '));
		for(int i=1; i<=N; i++) cc[i][0]=s[i-1];
		for(int i=1; i<=M; i++) cc[0][i]=t[i-1];

		int up[32][32];//各セルの前半要素が上の場合:1、左の場合:0
		memset(up, -1, sizeof(up));
		for(int i=1; i<=N; i++) up[i][0]=0;//使わない
		for(int i=1; i<=M; i++) up[0][i]=1;//使わない
		for(int i=1; i<=N; i++) {
			for(int j=1; j<=M; j++) {
				for(ll k=0; k<len[i][j]; k++) {
					if(k>=len[i][j-1]) { up[i][j]=0; break; }//使わない
					if(k>=len[i-1][j]) { up[i][j]=1; break; }//使わない
					vector <ll> u, l;
					u.push_back(i-1); u.push_back(j); u.push_back(k);
					l.push_back(i); l.push_back(j-1); l.push_back(k);
					while(1) {
						if(u==l) {//枝刈り(同じセルに到達)
							k+=len[u[0]][u[1]]-1;
							break;
						}
						if((u[0]==0 || u[1]==0) && (l[0]==0 || l[1]==0)) {
							if(cc[u[0]][u[1]]<cc[l[0]][l[1]]) up[i][j]=1;
							else up[i][j]=0;
							break;
						}
						if(u[0]>0 && u[1]>0) update(u, len, up);
						if(l[0]>0 && l[1]>0) update(l, len, up);
					}
					if(up[i][j]>=0) break;
				}
			}
		}

		for(ll i=pos; i<pos+50 && i<len[N][M]; i++) {
			vector <ll> u;
			u.push_back(N); u.push_back(M); u.push_back(i);
			while(1) {
				if(u[0]==0 || u[1]==0) {
					res.push_back(cc[u[0]][u[1]]);
					break;
				}
				update(u, len, up);
			}
		}

		return res;
	}
};
トラックバック - http://topcoder.g.hatena.ne.jp/jackpersel/20110626