TopCoder SRM 722 Div1 Easy: TCPhoneHome

するめうめ

tsutaj.hatenablog.com

問題概要

原文 → TopCoder Statistics - Problem Statement

leading zero を許して 桁の数字を作ることを考える。

文字列がいくつか与えられる。作る数字の prefix は、この文字列のいずれとも一致してはならない。

この状況下において、作れる数字はいくつあるか？

解説

余事象を考えて、作ることができない数字の総数を桁 DP したくなりそうな問題ですが、ある文字列が他の文字列の prefix と一致している場合に面倒なことが起こります。

実は、文字列 が文字列 の prefix と一致する場合、 は捨ててしまって構いません。なぜなら、 と一致するように (作れない数字になるように) 頑張っている最中に、自然と についても満たしているからです。

捨てられずに残った文字列どうしは、一方がもう一方の prefix になることはありません。

ここまで来るととてもシンプルで、作る数字の桁を とするとき、文字列 の制約上作ることができない数字が 個あり、また他の文字列の影響を受けないことから、 からこれを順次引くことによって答えを求められます。

ソースコード

long long int pw[20];
bool no_use[60];
class TCPhoneHome {
    public:
    long long validNumbers(int digits, vector<string> specialPrefixes) {
        memset(no_use, false, sizeof(no_use));

        int N = specialPrefixes.size();
        for(int i=0; i<N; i++) {
            for(int j=0; j<N; j++) {
                if(i == j) continue;
                if(specialPrefixes[i].size() > specialPrefixes[j].size()) continue;
                int len = specialPrefixes[i].size();
                if(specialPrefixes[j].substr(0, len) == specialPrefixes[i]) {
                    no_use[j] = true;
                }
            }
        }

        pw[0] = 1;
        for(int i=0; i<digits; i++) {
            pw[i+1] = pw[i] * 10;
        }

        long long int ans = pw[digits];
        for(int i=0; i<N; i++) {
            if(!no_use[i]) {
                ans -= pw[digits - (int)specialPrefixes[i].length()];
            }
        }
        return ans;
    }
};