Hatena::Grouptopcoder

SRM diary(Sigmar)

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

2012-01-15SRM529 Div1

SRM529 Div1 250 KingSort

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

Problem Statement

コーディングフェーズ

面倒くさい系か

ローマ数字の部分はパースとかすると絶対場合分けでハマりそうだから50種類しかないし全部列挙するのが楽だろう

書いた

mapとか使ったせいか意外と長いコードになってしまった


ソースコード

string one[9]={"I", "II", "III", "IV", "V", "VI", "VII", "VIII", "IX"};
string ten[5]={"X", "XX", "XXX", "XL", "L"};

class KingSort {
public:
	vector <string> getSortedList(vector <string> kings) {
		vector <string> res;
		vector <string> roman;
		for(int i=0; i<9; i++) roman.push_back(one[i]);
		for(int i=0; i<5; i++) {
			roman.push_back(ten[i]);
			for(int j=0; j<9; j++) {
				roman.push_back(ten[i]+one[j]);
			}
		}
		map <string, int> romannum;
		for(int i=0; i<50; i++) romannum[roman[i]]=i+1;

		map <pair <string, int>, string> resmp;
		stringstream ss;
		int n=kings.size();
		for(int i=0; i<n; i++) {
			ss.clear(); ss.str(kings[i]);
			string name, num;
			ss >> name >> num;
			resmp[make_pair(name, romannum[num])]=kings[i];
		}

		for(map <pair <string, int>, string>::iterator mpi=resmp.begin(); mpi!=resmp.end(); mpi++) {
			res.push_back(mpi->second);
		}
		return res;
	}
};

SRM529 Div1 600 MinskyMystery

| 17:14 | SRM529 Div1 600 MinskyMystery - SRM diary(Sigmar) を含むブックマーク はてなブックマーク - SRM529 Div1 600 MinskyMystery - SRM diary(Sigmar) SRM529 Div1 600 MinskyMystery - SRM diary(Sigmar) のブックマークコメント

Problem Statement

コーディングフェーズ

プログラムの解析問題なんて初めて見た

要するに大まかには以下のようなプログラムということである

  • bag0の初期値N、bag1の初期値2
  • bag0がbag1で割り切れる場合、終了
  • bag0がbag1で割り切れない場合、bag1を1増やしてリトライ

途中で色々bag0とbag2で入れ替えたりbag1とbag3で入れ替えたりbag4に増やしたりしているが結局以下のように単純に計算できる

ll res=0;
if(N<=1) return -1;

//bag1を最大xまで増やす
//Nが素数の場合、x=Nとなる
ll x=2;
for(x=2; x*x<=N; x++) {
	if(N%x==0) break;
}
if(N%x!=0) x=N;

res+=x; //bag1を1ずつxまで増やす部分
res+=N*4*(x-2); //bag0, bag1をbag2, bag3と入れ替える部分(x-2ターン分)
res+=N*3; //最終ターンのみbag2をbag0に戻さないので別計算する
for(ll i=2; i<=x; i++) res+=(N+i-1)/i; //bag4を増やす部分。各ターンにつきN/i、余りが出る場合更に1ターンでこの計算になる

return (int)res;

ここまで解析するのも大変だが、ここで問題となるのは、(N+i-1)/iを最大N回加算するため大きい素数のNでTLEするということである

O(1)で計算するのは多分難しいのだがO(√N)くらいに効率化するのはそんなに難しくなくて、(N+i-1)/iが同じ値になるものをまとめて加算すればいい

ここでは、(N+i-1)とiの差は常にN-1であるため、target=(N-1)/iとして、ni=(N-1)/targetが(N-1)/ni==(N-1)/iとなる最大のiである

したがってni=(N-1)/target+1とすることで、(ni-i)個の(N+i-1)/iを解に加算し、i=niとしてイテレーションを続ければいい

(概念は難しくないが、niの計算は難しい・・・)

これで計算量はO(√N)となる。

(√Nまでは1刻み、そこからは段々スカスカにiが増えていくが、N/iを見ると1刻みになるため2*√N程度になるはず)


書いた

すごい時間がギリギリになった。残り30秒で提出。

終了後よく見たら普通にオーバーフローしている場所がある。iがllじゃなくてintになってますが・・・


チャレンジフェーズで速攻で落とされる。何かもったいなかった。。


ソースコード

後で見たら4箇所もオーバーフローしててダメダメだった。

オーバーフローなんて初歩的なミスだが気をつけているつもりでもこんなに発生するなんて・・・

以下は修正版です。

const int MOD=1000000009;

class MinskyMystery {
public:
	int computeAnswer(long long N) {
		ll res=0;
		if(N<=1) return -1;

		ll x=2;
		for(x=2; x*x<=N; x++) {
			if(N%x==0) break;
		}
		if(N%x!=0) x=N;

		res=(res+x)%MOD;
		res=(res+N*4%MOD*((x-2)%MOD)%MOD)%MOD;
		res=(res+N*3%MOD)%MOD;
		for(ll i=2; i<=x; i++) {
			ll tdiv=(N+i-1)/i;
			ll target=tdiv-1;
			ll ni;
			if(target==0) ni=i+1;
			else {
				ni=(N-1)/target+1;
				ni=min(ni, x+1);
			}
			res=(res+tdiv%MOD*((ni-i)%MOD)%MOD)%MOD;
			i=ni-1;
		}

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