Hatena::Grouptopcoder

yuyarinのtopcoder記

TopCoder, Google Code JamPKU JudgeOnlineICPC などのアルゴリズム系プログラミングコンテストの参加や練習の記録を残していきます.

アルゴリズムやテーマで分類した目次はこちら

2010/03/20

SRM 464 ColorfulStrings

| 21:19

http://www.topcoder.com/stat?c=problem_statement&pm=10724&rd=14149

Sample Case: passed

System Test: passed

問題の条件から

  • 2桁以上の数字では0と1が入ってはいけない
  • 同じ数字は2回現れない

ということがわかるので 2<=n<=8 で考えればいいことがわかるので,ひとまず枝刈りをせずに 2,3,4,5,6,7,8,9 を辞書順で生成していき colorful かチェックする.結果的に枝刈りをしなくても実行速度は十分であった.

数字は整数配列 num[] で各桁を表現する.

辞書順の生成は再帰を使う (rec()).ある数字が使われたかを ap[] で記録しておき,使われていない数字を小さい方から num[pos] に入れていく.pos を 1 増やして再帰する.長さが桁数に達したら colorful かチェックを行う (colorful()).

colorful のチェックではそれまでの数字の積を記録 (mr[]) しておけば,ループを1重減らすことができる.

積のデータベースには set を利用している.insert() は既に要素があったときに .second で false が返されるので,既に積が出現している=colorful ではない場合を挿入と同時に判定できる.

あんまりスマートなコードだとは思わないけど,理解はしやすいと思う.

上位のコードはもっとシンプルだけどまだ解読出来ていない...

#include <cstdio>
#include <string>
#include <vector>
#include <iostream>
#include <sstream>
#include <set>

using namespace std;
inline int toi(string s){int v; istringstream iss(s);iss>>v;return v;}
template<class T> inline string tos(T x){ostringstream oss;oss<<x;return oss.str();}

class ColorfulStrings
{
public:

bool colorful(int n, int* num)
{
	// the results of mul
	int mr[] = {1,1,1,1,1,1,1,1,1,1,};
	
	set<int> m;
	
	for(int len=1; len<=n; ++len)
	{
		for(int idx=0; idx<=n-len; ++idx)
		{
			mr[idx] *= num[idx+len-1];
			if(!m.insert(mr[idx]).second)
				return false;
		}
	}
	
	return true;
}

bool rec(int n, int k, int* num, int* ap, int pos, int &cnt)
{
	if(pos==n)
	{
		if(colorful(n, num)) cnt++;
		if(cnt==k) return true;
		return false;
	}
	
	for(int i=2; i<10; ++i)
	{
		if(ap[i]) continue;
		num[pos] = i;
		ap[i] = 1;
		if(rec(n, k, num, ap, pos+1, cnt)) return true;
		ap[i] = 0;
	}
	return false;
}

string getKth(int n, int k)
{
	if(n>8) return "";
	if(n==1) return (k>10) ? "" : tos(k-1);
	
	string s = "";
	int num[8];
	int ap[] = {0,0,0,0,0,0,0,0,0,0};
	int cnt = 0;
	
	if(rec(n, k, num, ap, 0, cnt))
	{
		for(int i=0; i<n; ++i) s += num[i]+'0';
	}
	return s;
}
	
	
};

ElenaElena2013/02/17 05:39That addresses several of my concerns acutlaly.

sdxtpjsdxtpj2013/02/18 07:467hgOED , [url=http://vkhpudkqbafn.com/]vkhpudkqbafn[/url], [link=http://ibikxlgbdgkx.com/]ibikxlgbdgkx[/link], http://trdttgtbmydr.com/

beidpbknybeidpbkny2013/02/19 14:45wqJCeV <a href="http://pkzbvtmxkrzw.com/">pkzbvtmxkrzw</a>

hcaepwobinzhcaepwobinz2013/02/19 20:07MApC6d , [url=http://desrxojmthft.com/]desrxojmthft[/url], [link=http://qcvljhvzomoh.com/]qcvljhvzomoh[/link], http://socvhhjtbmkl.com/