SRM 464 DIV 2 その２

撃墜された500を清書してみた。
ちょっと書き換えてみたけど結局システムテストで落とされた＼(＾O＾)／

[方針]

n桁の全ての数に対してcolorfulかどうかのチェックをして、

colorfulだった場合カウンターをインクリメントしていって

k番目のcolorfulstringを見つけたらそれを返す。

方針と呼べるたいそうなものではないなぁ。。。全探索っていうのか？

colorfulかどうかのチェックは以下のように行う。

1. 0か1が含まれる場合、colorfulではないのでfalseを返す

2. 同じ数が２つ以上含まれる場合も、colorfulではないのでfalseを返す

3. product valueを格納するset Sを用意する

4. substringのproduct value Pを生成する

5. PがSに含まれればfalseを返す

6. PがSに含まれなければS.insert(P)とする

7. 4に戻る

TLEになっちゃうんだよなぁ。。。
substringの数は最大の８桁の場合でも36個で、８桁の数は全部で10^8-10^7=90000000個だから。。。だめなのか＞＜

#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <climits>
#include <cfloat>
#include <map>
#include <utility>
#include <set>
#include <iostream>
#include <memory>
#include <string>
#include <vector>
#include <algorithm>
#include <functional>
#include <sstream>
#include <complex>
#include <stack>
#include <queue>
using namespace std;
static const double EPS = 1e-5;
typedef long long ll;

class ColorfulStrings {
public:
    bool colorful(int num, int n) {
	set<int> S;
	string numstr = int2str(num, n);
	int used[10];
	memset(flag, 0, sizeof(flag));
	for (int i = 0; i < n; ++i) {
	    if (numstr[i] == '0' || numstr[i] == '1') return false; // 0か1が含まれればcolorfulではない
	    if (used[numstr[i]-'0'] == 0) used[numstr[i]-'0'] = 1;
	    else return false;
	}
	for (int i = 0; i < n; ++i) {
	    for (int j = 0; i+j < n; ++j) {
		int p = 1;
		for (int k = i; k <= i+j; ++k) {
		    p *= numstr[k] - '0';
		}
		if (S.find(p) == S.end()) S.insert(p);
		else return false; // pがすでにあればcolorfulではない
	    }
	}
	return true;
    }

    /* int -> string変換
     */
    string int2str(int num, int n) {
	int keta = 1;
	string ret = "";
	for (int i = 0; i < n-1; ++i) {
	    keta *= 10;
	}
	for ( ; keta >= 1; keta/=10) {
	    ret += num / keta + '0';
	    num %= keta;
	}
	return ret;
    }
    
    string getKth(int n, int k) {
	string result = "";
	if (n > 8) return result; // ９桁以上ではcolorfulになりえない
	if (n == 1) { // １桁の場合は特殊
	    if (k >= 1 && k <= 10) {
		result += (k-1) + '0';
		return result;
	    } else {
		return result;
	    }
	}
	int target; // colorfulかどうかチェックを行う数
	int goal; // 終点
	target = 1;
	goal = 10;
	for (int i = 0; i < n-1; ++i) {
	    target *= 10;
	    goal *= 10;
	}
	if (k > goal - target) return "";
	int cnt = 0;
	bool flag = false;
	for ( ; target < goal; ++target) {
	    if (colorful(target, n)) ++cnt; // targetがcolorfulならばcntをインクリメント
	    if (cnt == k) { // k番目のcolorful stringがみつかればループを抜ける
		flag = true;
		break;
	    }
	}
	if (flag) {
	    result = int2str(target, n);
	    return result;
	}
	else return result;
    }
};