Hatena::Grouptopcoder

SRM diary(Sigmar)

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

2011-06-05Google Code Jam 2011 Round 2

Google Code Jam 2011 Round 2 C Expensive Dinner

| 21:25 | Google Code Jam 2011 Round 2 C Expensive Dinner - SRM diary(Sigmar) を含むブックマーク はてなブックマーク - Google Code Jam 2011 Round 2 C Expensive Dinner - SRM diary(Sigmar) Google Code Jam 2011 Round 2 C Expensive Dinner - SRM diary(Sigmar) のブックマークコメント

Problem Statement

解答方針

取り掛かった時点で残り45分

とりあえずウェイターを呼んだ回数=客が注文した回数かと思い20分ほど考えたが全然分からない

よくよくExplanationを読んだところ、全然注文した回数とcallした回数が一致してない

再度問題をよく読むと、客が入ってきた時点で新しいウェイターが呼ばれ、全員満足するまでその人が注文を受け付けるらしい

ということは一人のウェイターが最大何回注文を受け付けるのか、の最小と最大を求めるのか

でも合わない

さらに20分くらい経って、ようやくウェイターが呼ばれるのが客が入ってきたときだけだということに気づいた

この時点で残り5分

とりあえずNから1の順と1からNの順でlcmを取って差分を求めてみた

そもそもlcmがオーバーフローして話にならない

だめだ

終了


後で

そもそも読み違えすぎ。(問題自体も分かりにくいと思うのだが・・)

「新しい客が入店時ウェイターを呼ぶことになる回数を求める」とか書いてほしかった


Aさんが入店したときに、それまでのlcmをLとしてlcm(A, L)!=Lのとき、ウェイターが呼ばれることになる

別の言い方をすると、Aを素因数分解して、Lの素因数分解に含まれないものがあった場合ウェイターが呼ばれる

最終的には、lcm(1~N)がトータルコストになるので、これを素因数分解することが重要

lcm(1~N)を素因数分解して、指数が1のものはその素数をもつ人が入店したときにウェイターが呼ばれ、それ以降呼ばれない

指数が2以上のものは、それまでに指数がnだったとすると、nより大きい指数をもつ人が入店したときにウェイターが呼ばれる

従って指数が1->2->3->...->nの順に呼ぶと最大でn回ウェイターが呼ばれ、逆順だと最小で1回しか呼ばれない

指数が2以上のものを対象に計算するので、√Nまでの素数を全て求め、N以下の最大指数を求めれば、(指数-1の和)+1が答えとなる

(最後の+1は、最初に1の人が入店すると+1されるため)

N==1のときだけ例外で、解は0となる


ソースコード

class GCJ {
	vector <int> vn;
public:
	void cpn(int n) {
		vn.assign(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;
		}
	}

	ll solve(ll N) {
		ll res=0;
		if(N==1) return 0;

		for(ll i=2; i*i<=N; i++) {
			if(!vn[i]) continue;
			ll mul=i*i;
			ll cnt=0;
			while(mul<=N) {
				mul*=i;
				cnt++;
			}
			res+=cnt;
		}
		res++;
		return res;
	}
};

int main() {
	ifstream ifs("input.txt");
	ofstream ofs("output.txt");

	GCJ gcj;
	gcj.cpn(1000010);
	int testcase;
	ifs >> testcase; ifs.ignore();
	for(int testnum=1; testnum<=testcase; testnum++) {
		ll N;
		ifs >> N;
		ll res=gcj.solve(N);
		ofs << "Case #" << testnum << ": ";
		ofs << res << endl;
	}
}
トラックバック - http://topcoder.g.hatena.ne.jp/jackpersel/20110605