Hatena::Grouptopcoder

SRM diary(Sigmar)

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

2010-12-09SRM490 Div1

SRM490 Div1 250 Starport

| 01:48 | SRM490 Div1 250 Starport - SRM diary(Sigmar) を含むブックマーク はてなブックマーク - SRM490 Div1 250 Starport - SRM diary(Sigmar) SRM490 Div1 250 Starport - SRM diary(Sigmar) のブックマークコメント

Problem Statement

コーディングフェーズ

任意のkに対してk*M%NはGCD(N,M)の倍数にしかならないことを経験則で知っていたので見た瞬間解法が分かった

つまり、g=GCD(N,M)とすると、0,g,2*g,3*g,...,N-gの平均が答えだ。

等差数列の和を要素数で割れば良い。

→書く

→サンプル合わない

計算ミスしてた

→直す

ふむ。。。そうか、等差数列の平均値だから、(最小値+最大値)/2でいいんだ。

→サンプル合う

→提出

あれ・・ほとんど誰も出してない

大丈夫だよな・・

N<Mのパターンとか色々試す

やっぱり問題なさそう

→500へ


チャレンジフェーズ

ややこしい数式書いている人が多いなあ

怪しいが合ってるかよく分からない。

突込みどころなし・・・


システムテスト

Passed


ソースコード

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

class Starport {
public:
	double getExpectedTime(int N, int M) {
		double res;

		double g=gcd(N, M);
		double sum=N-g;
		res=sum/2;
		return res;
	}
};

SRM490 Div1 550 QuickT9

| 01:48 | SRM490 Div1 550 QuickT9 - SRM diary(Sigmar) を含むブックマーク はてなブックマーク - SRM490 Div1 550 QuickT9 - SRM diary(Sigmar) SRM490 Div1 550 QuickT9 - SRM diary(Sigmar) のブックマークコメント

Problem Statement

コーディングフェーズ

要は各Fについて最短の手数を求めるところが肝

なんか色々難しく考えすぎて書いている内に時間切れになった

みんなよく時間内に書けるなあ・・・


後で

落ち着いて整理すれば、各Fの最短手順を求めるのはそんなに難しくない

入力文字数(数字の数)+辞書順番(*の数)+クリア文字数(Cの数)みたいな感じでmap <string, int>を使って最小値を求めればOKだった

あとは簡単なDP


実装系はまだまだ力不足ですが落ち着いて整理することが重要ですね・・・


ソースコード

システムテストは通ります

int memo[52];

template <class T> vector <T> strspl(string str) {
	vector <T> res;
	istringstream iss(str);
	copy(istream_iterator <T>(iss), istream_iterator <T>(), back_inserter(res));
	return res;
}

class QuickT9 {
public:
	int n, m;
	vector <string> words, nwords;
	string word;
	map <string, int> Fcnt;

	int rec(int d) {
		int res=1000000000;

		if(d==m) return 0;
		if(memo[d]>=0) return memo[d];

		for(int i=0; d+i<=m; i++) {
			string s=word.substr(d, i);
			if(!Fcnt.count(s)) continue;
			res=min(res, rec(d+i)+Fcnt[s]);
		}

		memo[d]=res;
		return res;
	}

	char ltob(char c) {
		if(c>='a' && c<='c') return '2';
		if(c>='d' && c<='f') return '3';
		if(c>='g' && c<='i') return '4';
		if(c>='j' && c<='l') return '5';
		if(c>='m' && c<='o') return '6';
		if(c>='p' && c<='s') return '7';
		if(c>='t' && c<='v') return '8';
		return '9';
	}
		
	int minimumPressings(vector <string> t9, string word) {
		int res;
		for(int i=0; i<(int)t9.size(); i++) {
			vector <string> vs=strspl <string>(t9[i]);
			words.insert(words.end(), vs.begin(), vs.end());
		}
		words.erase(unique(words.begin(), words.end()), words.end());
		n=words.size();
		this->word=word;
		m=word.size();
		memset(memo, -1, sizeof(memo));

		//各単語のDの表現を求める
		nwords.assign(n, string());
		for(int i=0; i<n; i++) {
			for(int j=0; j<(int)words[i].size(); j++) {
				nwords[i].push_back(ltob(words[i][j]));
			}
		}
		//各DについてUの集合をマップする
		map <string, set <string> > DtoU;
		for(int i=0; i<n; i++) {
			for(int j=1; j<=(int)nwords[i].size(); j++) {
				DtoU[nwords[i].substr(0, j)].insert(words[i].substr(0, j));
			}
		}

		//各Fの最短手順を求める
		Fcnt.clear();
		for(map <string, set <string> >::iterator mpi=DtoU.begin(); mpi!=DtoU.end(); mpi++) {
			int cnt=1;
			for(set <string>::iterator ssi=mpi->second.begin(); ssi!=mpi->second.end(); ssi++) {
				int cost=mpi->first.size()+cnt;
				if(!Fcnt.count(*ssi) || Fcnt[*ssi]>cost) Fcnt[*ssi]=cost;
				for(int i=1; i<(int)(*ssi).size(); i++) {
					string s=(*ssi).substr(0, (*ssi).size()-i);
					if(!Fcnt.count(s) || Fcnt[s]>cost-1+i) Fcnt[s]=cost-1+i;
				}
				cnt++;
			}
		}

		res=rec(0);
		if(res>=1000000000) res=-1;
		return res;
	}
};
トラックバック - http://topcoder.g.hatena.ne.jp/jackpersel/20101209