Hatena::Grouptopcoder

SRM diary(Sigmar)

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

2012-05-13TCO2012 Round2B

TCO2012 Round2B 300 BlurredDartboard

| 17:55 | TCO2012 Round2B 300 BlurredDartboard - SRM diary(Sigmar) を含むブックマーク はてなブックマーク - TCO2012 Round2B 300 BlurredDartboard - SRM diary(Sigmar) TCO2012 Round2B 300 BlurredDartboard - SRM diary(Sigmar) のブックマークコメント

Problem Statement

コーディングフェーズ

300とか嫌な予感しかしない

と思ったが珍しくやるだけの予感

見えてる中で最高得点の的と見えない的の平均値で比較していい方を採用する

見えない方は最後の余りは平均でなく小さい方から選ぶことになることに注意する

書いた

例外が発生しました: Integer division by zero

サンプル親切・・・!


直した

合わない

やっぱ300だしこんな単純じゃなかった?/(^o^)\ナンテコッタイ


分からん

デバッガ起動


添字誤りだった

本当につまらないミスが多い・・・


提出


ソースコード

class BlurredDartboard {
public:
	int minThrows(vector <int> points, int P) {
		int res;
		int n=points.size();

		int maxscore=0;
		for(int i=0; i<n; i++) maxscore=max(maxscore, points[i]);
		if(maxscore>0) res=(P+maxscore-1)/maxscore;
		else res=1000000001;

		int zerocnt=0;
		vector <int> zero;
		int used[52]={0};
		for(int i=0; i<n; i++) if(points[i]) used[points[i]]=1;
		for(int i=1; i<=n; i++) if(!used[i]) zero.push_back(i);
		zerocnt=zero.size();

		if(zerocnt>0) {
			int tot=0;
			for(int i=0; i<zerocnt; i++) tot+=zero[i];
			int tres=P/tot*zerocnt;
			int rem=P%tot;
			int inc1=0;
			if(maxscore>0) inc1=(rem+maxscore-1)/maxscore;
			else inc1=1000000001;
			int inc2=0;
			int sum=0;
			for(int i=0; i<zerocnt; i++) {
				if(sum>=rem) break;
				inc2++;
				sum+=zero[i];
			}
			tres+=min(inc1, inc2);
			res=min(res, tres);
		}
		
		return res;
	}
};

TCO2012 Round2B 550 HeavyBooks

| 17:55 | TCO2012 Round2B 550 HeavyBooks - SRM diary(Sigmar) を含むブックマーク はてなブックマーク - TCO2012 Round2B 550 HeavyBooks - SRM diary(Sigmar) TCO2012 Round2B 550 HeavyBooks - SRM diary(Sigmar) のブックマークコメント

Problem Statement

コーディングフェーズ

うーん

一番重いのを押し付けあうとしか思えない

それより軽いのを渡しても得する場面が全く思いつかない


一番重いのを押し付けあうとすると、最初にTomekがどの本を入れるか決めるだけの問題

重い順に見ていけばどちらが持つかは一意に決まるので、重い順に本を採用するかしないかでDPすればOKかな


書こうとする

添字とDPの更新条件式がカオスになる

デバッグで最終的に40分もかかった


提出


ソースコード

DP更新条件式のカオスなところは直しました

今回はpairを使えば比較的ラクに更新ができる気がする

本番でもpairを使っていたのになぜカオスになったんだ・・・

const int INF=1000000000;

class HeavyBooks {
public:
	vector <int> findWeight(vector <int> books, vector <int> moves) {
		vector <int> res;
		int n=books.size();
		int m=moves.size();

		vector <int> b(moves[0], 1);
		for(int i=1; i<m; i++) {
			int idx=0;
			for(int j=0; j<moves[0]; j++) {
				if(b[j]==(i&1)) {
					b[j]=1-b[j];
					idx++;
					if(idx==moves[i]) break;
				}
			}
		}

		pair <int, int> difsum[52][52];
		for(int i=0; i<52; i++) for(int j=0; j<52; j++) {
			difsum[i][j]=make_pair(-INF, 0);
		}
		difsum[0][0]=make_pair(0, 0);
		sort(books.begin(), books.end(), greater <int>());
		for(int d=0; d<n; d++) {
			for(int bi=0; bi<moves[0]; bi++) {
				pair <int, int> cand;
				cand=difsum[d][bi];
				difsum[d+1][bi]=max(difsum[d+1][bi], cand);
				if(b[bi]) {
					cand=difsum[d][bi];
					cand.first+=books[d]; cand.second+=books[d];
					difsum[d+1][bi+1]=max(difsum[d+1][bi+1], cand);
				} else {
					cand=difsum[d][bi];
					cand.first-=books[d]; cand.second+=books[d];
					difsum[d+1][bi+1]=max(difsum[d+1][bi+1], cand);
				}
			}
		}
		pair <int, int> best(-INF, 0);
		for(int i=0; i<=n; i++) {
			best=max(best, difsum[i][moves[0]]);
		}
		
		res.push_back((best.second-best.first)/2);
		res.push_back((best.first+best.second)/2);
		return res;
	}
};
トラックバック - http://topcoder.g.hatena.ne.jp/jackpersel/20120513

2012-04-22TCO2012 Round2A

TCO2012 Round2A 300 SwitchesAndLamps

| 17:48 | TCO2012 Round2A 300 SwitchesAndLamps - SRM diary(Sigmar) を含むブックマーク はてなブックマーク - TCO2012 Round2A 300 SwitchesAndLamps - SRM diary(Sigmar) TCO2012 Round2A 300 SwitchesAndLamps - SRM diary(Sigmar) のブックマークコメント

コーディングフェーズ

以下の2つの問題に分けて考えればいい

  1. 与えられた情報から、スイッチとランプをこれ以上分割できないグループに分割する
  2. 各グループを更にスイッチ・ランプ1個ずつのグループまで分割するための最小テスト数を求める

時間をかけた挙句、1,2ともに間違った解答を出してしまいチャレンジされる


後で

1のほうは、実は縦に見て全く同じ結果のものを集めればいいだけだったりする

つまり、1回目のテストがY、2回目がN、3回目がYのスイッチがあったとすると、それと同じグループに入れるスイッチは、やはり1回目のテストがY、2回目がN、3回目がYのスイッチである。

同様に、ランプの全く同じパターンのものを集める。

1つのグループ内で、スイッチとランプの数が違っていたら-1。


2のほうは、とりあえず全てのグループに対し、並列で試験ができるので、一番スイッチ数の多いグループだけを考えればいい。

並列で試験できることを考えると、試験数を最小にするには、グループをYとNで2分割することである

分かれた2つのグループに対し同時に試験ができるから、さらに大きい方を2分割して・・・と続けていくと、いつかスイッチ数が1になる

これにかかる回数を出せばOK


ソースコード

試験結果の比較はstringでやればいいのだが、何かあまり整理しきれてないときに書いたコード

任意のスイッチorランプのペアに対して、1つでも結果が異なる試験があれば別グループという判定をしている

class SwitchesAndLamps {
public:
	int calc(ll cnt) {
		int res=0;
		while(cnt>1) {
			cnt=(cnt+1)/2;
			res++;
		}
		return res;
	}

	int theMin(vector <string> sw, vector <string> lmp) {
		int res;
		int esz=sw.size(), n=sw[0].size();

		int conn[102][102];
		for(int i=0; i<n*2; i++) for(int j=0; j<n*2; j++) conn[i][j]=1;
		for(int i=0; i<esz; i++) {
			for(int j=0; j<n; j++) {
				for(int k=j+1; k<n; k++) {
					if(sw[i][j]!=sw[i][k]) conn[j][k]=conn[k][j]=0;
					if(lmp[i][j]!=lmp[i][k]) conn[n+j][n+k]=conn[n+k][n+j]=0;
				}
				for(int k=0; k<n; k++) {
					if(sw[i][j]!=lmp[i][k]) conn[j][n+k]=conn[n+k][j]=0;
				}
			}
		}

		res=0;
		vector <int> used(n*2);
		for(int i=0; i<n; i++) {
			if(used[i]) continue;
			used[i]=1;
			int swcnt=1, lmpcnt=0;
			for(int j=i+1; j<2*n; j++) {
				if(!conn[i][j]) continue;
				assert(!used[j]);
				used[j]=1;
				if(j<n) swcnt++;
				else lmpcnt++;
			}
			if(swcnt!=lmpcnt) return -1;
			res=max(res, calc(swcnt));
		}

		return res;
	}
};

TCO2012 Round2A 450 CucumberWatering

| 17:48 | TCO2012 Round2A 450 CucumberWatering - SRM diary(Sigmar) を含むブックマーク はてなブックマーク - TCO2012 Round2A 450 CucumberWatering - SRM diary(Sigmar) TCO2012 Round2A 450 CucumberWatering - SRM diary(Sigmar) のブックマークコメント

コーディングフェーズ

どう見てもDPっぽい

テレポートポイントはcucumberの上にしか置かなかったとしても問題なさそうなのでそうする

普通にやれば、水をやる順番に進めたいところだが、そうするとどのcucumberの上に置いたか記憶するので2^50とかになるので無理

とすると、x座標で左から順にテレポートを置いていくとか考えるわけです

前にテレポートを置いた場所をptelとすると、現在の位置ctelに置いたとき、ptel~ctel間のcucumberはどんな距離を加算すれば良いでしょう

この辺で整理できなくなって時間切れになってしまった


後で

ptel~ctelの間にcucumber iがあったとき、次に水をやるcucumber i+1との距離と、前に水をやったcucumber i-1との距離をそれぞれ加算する

しかし、このとき基本的に最寄りのテレポートを経由して行くことにする。

ただし、i-1(またはi+1)がptel~ctelの間にあるときは、直接歩いたほうが早いかもしれない。

なので、その時は早いほうを採用する。

なお、i-1(またはi+1)がptel~ctelの間にないときは、必ずテレポートを経由して行っても直接歩くより時間がかかることはない。

(同じテレポートから出てくることも可能なため)

ということでDPが書けるので書く

かなり書くのしんどい


上位の人が軒並み200点台の中で、Petr見たら370点とかだった

アルゴリズム力もさることながら、ややこしいコードを素早く書く能力がずば抜けている・・・

Petr伝説


ソースコード

const ll INF=1000000000000000000LL;

class CucumberWatering {
public:
	long long theMin(vector <int> xx, int K) {
		long long res;
		int n=xx.size();
		vector <ll> x;
		x.push_back(-10000000000LL);//番兵(左端のテレポートポイント)
		for(int i=0; i<n; i++) x.push_back(xx[i]);
		x.push_back(10000000000LL);//番兵(右端のテレポートポイント)

		vector <pair <ll, int> > px;
		for(int i=0; i<n+2; i++) {
			px.push_back(make_pair(x[i], i));
		}
		sort(px.begin(), px.end());

		vector <int> rx(n+2);
		for(int i=0; i<n+2; i++) rx[i]=px[i].second;

		ll dp[53][53][53];
		for(int i=0; i<53; i++) for(int j=0; j<53; j++) for(int k=0; k<53; k++) dp[i][j][k]=INF;
		dp[1][0][0]=0;
		for(int ctel=1; ctel<=n+1; ctel++) {
			for(int ptel=0; ptel<ctel; ptel++) {
				for(int k=0; k<=min(ctel, K); k++) {
					if(ctel<=n) dp[ctel+1][ptel][k]=min(dp[ctel+1][ptel][k], dp[ctel][ptel][k]);
					if(ctel<=n && k==K) continue;//右端の番兵には必ずテレポートを設置する
					ll nval=dp[ctel][ptel][k];
					if(nval>=INF) continue;
					ll ptelpos=x[rx[ptel]], ctelpos=x[rx[ctel]];
					for(int i=ptel+1; i<=min(n, ctel); i++) {
						ll cpos=x[rx[i]];
						ll tdist=min(abs(cpos-ptelpos), abs(cpos-ctelpos));
						if(rx[i]>1) {
							ll ppos=x[rx[i]-1];
							if(ptelpos<ppos && ppos<ctelpos) {
								ll odist=abs(cpos-ppos);
								ll ptdist=min(abs(ppos-ptelpos), abs(ppos-ctelpos));
								if(odist<tdist+ptdist) nval+=odist;
								else nval+=tdist;
							} else nval+=tdist;
						}
						if(rx[i]<n) {
							ll npos=x[rx[i]+1];
							if(ptelpos<npos && npos<ctelpos) {
								ll odist=abs(cpos-npos);
								ll ntdist=min(abs(npos-ptelpos), abs(npos-ctelpos));
								if(odist<tdist+ntdist) nval+=0;//ppos側で加算したはず
								else nval+=tdist;
							} else nval+=tdist;
						}
					}
					dp[ctel+1][ctel][k+1]=min(dp[ctel+1][ctel][k+1], nval);
				}
			}
		}

		res=INF;
		for(int i=0; i<n+2; i++) for(int j=0; j<=K+1; j++) res=min(res, dp[n+2][i][j]);
		return res;
	}
};
トラックバック - http://topcoder.g.hatena.ne.jp/jackpersel/20120422

2012-04-01TCO2012 Round1A

TCO2012 Round1A 250 EllysJuice

| 16:30 | TCO2012 Round1A 250 EllysJuice - SRM diary(Sigmar) を含むブックマーク はてなブックマーク - TCO2012 Round1A 250 EllysJuice - SRM diary(Sigmar) TCO2012 Round1A 250 EllysJuice - SRM diary(Sigmar) のブックマークコメント

Problem Statement

コーディングフェーズ

予選にしては問題めんどくさああ

制約が小さいのでnext_permutationでナイーブにシミュレーションした

シミュレーションを省略するとよく間違えるので、本当にナイーブにシミュレーションした

提出

書くの遅っ と思ったら誰も出してなかった

みんな同様に律儀にシミュレーション書いていたみたい


チャレンジフェーズ

sortせずにnext_permutationしてる人を2人落とした

実は最後の返り値をsortしてない人も2人いたらしい。気づかなかった・・・


後で

シミュレーションしなくても、2回以上名前が出てくる人は必ず勝てる

オレンジとリンゴを50%ずつ取れば必ず勝てるので。後の人はどんなに頑張っても残りを全部取れるわけではないので、負ける

ただし一人しかいない場合に注意


ソースコード

ナイーブなシミュレーション

しかし後で見たらint ok=falseって・・・

warningにならないのね・・

class EllysJuice {
public:
	vector <string> getWinners(vector <string> pl) {
		vector <string> res;
		int n=pl.size();
		
		set <string> ress;
		sort(pl.begin(), pl.end());
		do {
			int o=32, a=32;
			map <string, int> cnt;
			for(int i=0; i<n; i++) {
				if(i&1) {cnt[pl[i]]+=a/2; a/=2; }
				else {cnt[pl[i]]+=o/2; o/=2; }
			}
			int maxc=-1;
			int ok=false;
			string winner;
			for(map <string, int>::iterator mpi=cnt.begin(); mpi!=cnt.end(); mpi++) {
				if(mpi->second>maxc) {
					maxc=mpi->second;
					winner=mpi->first;
					ok=true;
				} else if(mpi->second==maxc) {
					ok=false;
				}
			}
			if(ok) ress.insert(winner);
		} while(next_permutation(pl.begin(), pl.end()));

		for(set <string>::iterator sti=ress.begin(); sti!=ress.end(); sti++) {
			res.push_back(*sti);
		}
		return res;
	}
};

TCO2012 Round1A 500 EllysFractions

| 16:30 | TCO2012 Round1A 500 EllysFractions - SRM diary(Sigmar) を含むブックマーク はてなブックマーク - TCO2012 Round1A 500 EllysFractions - SRM diary(Sigmar) TCO2012 Round1A 500 EllysFractions - SRM diary(Sigmar) のブックマークコメント

Problem Statement

コーディングフェーズ

分母と分子は互いに素なわけだから、同じ素因数を持つことができない

ということは、これまでに出てきた全ての素因数を2つに分けるだけの問題

ただし分母>分子の制約があるので、最後に2で割る必要がある

2つに分けるっていったって、同じ素因数は全部同じ側に入れるので、2^(素因数の種類数)するだけである

素因数分解してsetに突っ込んでいくコードを書いた

提出


チャレンジフェーズ

2^(素因数の種類数)を32bitで計算している人がいたので撃墜


後で

実は素因数分解はする必要がなかった

2つ以上に分解できる場合は、必ず既にその素因数が登場しているはずなので、素数かどうかだけを判定すれば良い


ソースコード

素因数分解しているコード

//素因数分解
vector <ll> factors(ll n) {
	vector <ll> f;

	for(ll i=2; i*i<=n; i++) {
		int cnt=0;
		while(n%i==0) { n/=i; cnt++; }
		if(cnt>0) f.push_back(i);
	}
	if(n>1) f.push_back(n);

	return f;
}

class EllysFractions {
public:
	long long getCount(int N) {
		long long res;
		set <int> pr;

		res=0;
		for(int i=2; i<=N; i++) {
			vector <ll> f=factors(i);
			for(int j=0; j<(int)f.size(); j++) {
				pr.insert((int)f[j]);
			}
			res+=(1LL<<(pr.size()-1));
		}
		
		return res;
	}
};

TCO2012 Round1A 1000 EllysLights

| 16:30 | TCO2012 Round1A 1000 EllysLights - SRM diary(Sigmar) を含むブックマーク はてなブックマーク - TCO2012 Round1A 1000 EllysLights - SRM diary(Sigmar) TCO2012 Round1A 1000 EllysLights - SRM diary(Sigmar) のブックマークコメント

Problem Statement

コーディングフェーズ

1つのライトにつながるスイッチが最大2個っていうのがポイントだな

2個っていかにも2-SATっぽい

うーん

何か違う気もするなあ


というか、以前こんな感じの問題解いたことあるような・・・

(後で確認したら、SRM496 Div1 500 OneDimensionalBalls だった)

スイッチが2個しかないので、一つのスイッチを使うと、芋づる式に連結する他のスイッチのON/OFFが決まる

連結してるのは全部ひとまとまりで考えていいので、実は1つの連結成分ずつON/OFFを決めていけば状態数がすごく少ない

ということは適当にメモ化再帰すればいいんじゃないか


と思ったけどループするから再帰とか面倒くさい

BFSで書けばいいや・・・


書いた

うーん連結成分とか完全に無視して、前から1ビットずつ決める書き方にしちゃったけど大丈夫かなこれ・・

とりあえずサンプルは一瞬で答え出るので提出


ランダムな入力とか、全部のスイッチが連結している入力とか、色々試す

特に問題ない。一番やばそうなのでも手元で100ms以下。


チャレンジフェーズ

赤い人2人から合計3回もチャレンジ受けるが生き残る

ハニーポット状態になってしまった


システムテスト

通った。後でプラクティスで確認したらarenaでは最大で10msもかかっていない。


ソースコード

しかしこの書き方してる人、自分以外に見なかったのだが・・・

なぜだろう(一見TLEっぽいから?)

他の人はdfsしてたりunion-findしてたり色々

class EllysLights {
public:
	int getMinimum(string initial, vector <string> switches) {
		int res;
		vector <ll> sw;
		int sws, lts;
		sws=switches.size();
		lts=initial.size();

		for(int i=0; i<sws; i++) {
			ll v=0;
			for(int j=0; j<lts; j++) {
				if(switches[i][j]=='Y') v|=(1LL<<j);
			}
			sw.push_back(v);
		}

		ll ini=0;
		for(int i=0; i<lts; i++) {
			if(initial[i]=='Y') ini|=(1LL<<i);
		}

		queue <ll> q;
		q.push(ini);
		map <ll, int> memo;
		memo[ini]=0;
		while(!q.empty()) {
			ll qt=q.front(); q.pop();
			if(qt==0) break;
			for(int i=0; i<lts; i++) {
				if(qt&(1LL<<i)) {
					for(int j=0; j<sws; j++) {
						if(sw[j]&(1LL<<i)) {
							ll nv=qt^sw[j];
							if(!memo.count(nv)) {
								q.push(nv);
								memo[nv]=memo[qt]+1;
							}
						}
					}
					break;
				}
			}
		}
		
		if(!memo.count(0)) res=-1;
		else res=memo[0];
		return res;
	}
};

PutuPutu2012/11/14 17:34We've avrried at the end of the line and I have what I need!

qugzuwvdqugzuwvd2012/11/15 12:09hsO2Bf <a href="http://sgnsqmlhqiaa.com/">sgnsqmlhqiaa</a>

sbgfuadwnunsbgfuadwnun2012/11/17 11:17uDRxYO <a href="http://swfgvcnqwgxp.com/">swfgvcnqwgxp</a>

ppmzklppmzkl2012/11/17 20:51kG1Uk0 , [url=http://ybtvmgzaihcg.com/]ybtvmgzaihcg[/url], [link=http://hfpczhabiicm.com/]hfpczhabiicm[/link], http://gqoxvctjnvhq.com/

トラックバック - http://topcoder.g.hatena.ne.jp/jackpersel/20120401

2011-07-10TCO2011 Round3

TCO2011 Round3 250 ArtShift

| 14:47 | TCO2011 Round3 250 ArtShift - SRM diary(Sigmar) を含むブックマーク はてなブックマーク - TCO2011 Round3 250 ArtShift - SRM diary(Sigmar) TCO2011 Round3 250 ArtShift - SRM diary(Sigmar) のブックマークコメント

Problem Statement

解答方針

好きなようにpermutationできるのでWとBの順番はどうでもいい

循環させるグループに分類すれば終了


例えば{0,1,2,3,4}という順列があったとき、{1,0,4,2,3}というpermutationを作ると、{0,1}と{2,3,4}がそれぞれ循環する

このように循環させるグループに分けると、順番は任意にできるので例えばW1個B2個のグループならWBBといったようにWを左端に片寄せするような順番にすることが可能

なので1グループで最大でグループ要素数分のパターンがある

ただし全部同じ色だと1パターンしか取れない

以上が分かれば、Wの数とBの数で1つずつグループを決めてやるような書き方で計算量問題なし


ソースコード

ll gcd(ll a, ll b) {
	while(b) {
		a=a%b;
		swap(a, b);
	}
	return a;
}

ll lcm(ll a, ll b) {
	return a/gcd(a,b)*b;
}

int memo[32][32][10000];

class ArtShift {
public:
	int rec(int w, int b, int lcmv) {
		if(memo[w][b][lcmv]>=0) return memo[w][b][lcmv];
		int res=lcmv;

		if(w==0 || b==0) return res;
		for(int i=1; i<=w; i++) {
			for(int j=1; j<=b; j++) {
				int nlcmv=lcm(lcmv, i+j);
				res=max(rec(w-i, b-j, nlcmv), res);
			}
		}

		memo[w][b][lcmv]=res;
		return res;
	}

	int maxShifts(string seq) {
		int n=seq.size();
		if(n==1) return 1;

		int w=0, b=0;
		for(int i=0; i<n; i++) if(seq[i]=='W') w++; else b++;
		if(w>b) swap(w, b);
		if(w==0) return 1;

		memset(memo, -1, sizeof(memo));
		int res=rec(w, b, 1);

		return res;
	}
};

TCO2011 Round3 500 PrefixFreeSuperset

| 14:47 | TCO2011 Round3 500 PrefixFreeSuperset - SRM diary(Sigmar) を含むブックマーク はてなブックマーク - TCO2011 Round3 500 PrefixFreeSuperset - SRM diary(Sigmar) TCO2011 Round3 500 PrefixFreeSuperset - SRM diary(Sigmar) のブックマークコメント

Problem Statement

解答方針

実装問題的な感じ

既存のwordに対し2分木を作ってやる

あとは空いているところを使って木の高さを平準化しながら必要なだけ高さを増やしていくだけ

「空いているところを使って」というのが意外と難しいと思う


ソースコード

newとか使ってdeleteしていないからメモリリークを起こしている気がする

なるべくnewとか使いたくないものだ

class PrefixFreeSuperset {
public:
	struct node {
		node *child[2];
	};

	int ways[150];

	void calc(int d, node *x) {
		if(x->child[0]==NULL && x->child[1]==NULL) return;

		if(x->child[0]!=NULL) calc(d+1, x->child[0]);
		else ways[d]++;
		if(x->child[1]!=NULL) calc(d+1, x->child[1]);
		else ways[d]++;
	}

	void construct(node *x, string s, int d) {
		if(d>=(int)s.size()) return;
		int nc=s[d]-'0';
		if(x->child[nc]==NULL) {
			x->child[nc]=new node;
			x->child[nc]->child[0]=NULL; x->child[nc]->child[1]=NULL;
		}
		construct(x->child[nc], s, d+1);
	}

	long long minSumLength(vector <string> cur, long long k) {
		long long res;
		int n=cur.size();

		node *root=new node;
		root->child[0]=NULL; root->child[1]=NULL;
		for(int i=0; i<(int)cur.size(); i++) {
			construct(root, cur[i], 0);
		}

		memset(ways, 0, sizeof(ways));
		calc(0, root);

		res=0;
		for(int i=0; i<n; i++) res+=cur[i].size();
		if(k==n) return res;

		bool ok=false;
		for(int i=0; i<150; i++) if(ways[i]>0) ok=true;
		if(!ok) return -1;

		ll sum=0;
		int h=0;
		while(sum*2+ways[h]<k-n) {
			sum=sum*2+ways[h];
			h++;
		}
		res+=(k-n)*h;
		if(k-n-sum<=ways[h]) res+=k-n-sum;
		else res+=ways[h]+(k-n-sum-ways[h])*2;

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

2011-06-26TCO2011 Round2

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