hogecoder

つたじろう(Tsuta_J) 競技プログラミングの記録

TopCoder SRM 722 Div1 Easy: TCPhoneHome

するめうめ

tsutaj.hatenablog.com

問題概要

原文 → TopCoder Statistics - Problem Statement

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

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

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

解説

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

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

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

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

ソースコード

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;
    }
};