SRMとか春合宿とか

明日(3/19)からサークルの春合宿。90分の講座をやらねばならんので淡々と準備中…。間に合う予定だけど発表時間どうなることやら…。

TopCoderはSRM 464でスコアが1416->1452と微増。
チャレンジ失敗したり提出一回やり直したりとしてたらポイントが…、うっう…(泣)。

頑張って2問解けるようになりたいなぁと思いつつ、それなら終わったあとも練習するとかする努力をしないといけないんだけどやってねー…。ぐぬぬー。
せっかくなので250(ColorfulStrings)のコードを貼っておく。

…貼ってから気付いたがかなり酷いコード+富豪だなーと思った。うーむ…。
next_permutation連打しまくってるのってどうなんだ…。あとgetKthの先頭はかなり荒いというか見てて心が挫けそうになる…。あとで見ても病まないものを書きたい…。

class ColorfulStrings {
public:
    int product(string s) {
        int ret = 1;
        for (int i=0; i<(int)s.length(); ++i) {
            ret *= s[i]-'0';
        }
        return ret;
    }
    bool check(string s, int n, int k) {
        bool b[362880+1];
        memset(b, 0, sizeof(b));
        for (int i=1; i<=n; ++i) {
            for (int j=0; i+j<=n; ++j) {
                int x = product(s.substr(j, i));
                if (b[x]) {
                    return false;
                } else {
                    b[x] = true;
                }
            }
        }
        return true;
    }
    string getKth(int n, int k) {
        if (n >= 9) { return ""; }

        string s, prev="";
        if (n == 1) {
            if (k > 10) { return "";}
            else { string s = "0"; s[0] = '0'+k-1; return s;}
        }
        else if (n == 2) {
            s = "0123456789";
        } else {
            s = "23456789";
        }

        int tmp = 1;
        for (int l=0; l<n; ++l) {
            tmp *= 10-l;
        }
        if (tmp < k) { return ""; }

        int i=0;
        do {
            if (s.substr(0, n) == prev) { continue; }
            if (check(s, n, k)) {
                ++i;
                if (i == k) {
                    return s.substr(0, n);
                }
            }
            prev = s.substr(0, n);
        } while (next_permutation(s.begin(), s.end()));

        return "";
    }
};