mayoko’s diary

プロコンとかいろいろ。

SRM 649 div1 easy: Decipherability

勘が冴えた感じがあって240点取れた。

問題:http://community.topcoder.com/stat?c=problem_statement&pm=13656&rd=16313

解法:N=(sの長さ)とする。N==Kのときは当然消した文字をすべて特定できる。K < Nのときは、特定できない可能性があるが、それはどういう時かというと、文字cが場所p, q(p < q)にある時、q-p <= Kとなる時である。なぜかというと、q-p <= Kの時、q番目の文字を残しながらp,p+1,...q-1番目の文字を消すことができるからである。すると、残った文字列を見た時、文字cがp番目にあったものかq番目にあったものか特定することができない。逆に、すべての文字についてq-p > Kが成り立つとすると、K文字消しても必ず同じ文字同士の順序関係が固定されるので完全に特定できる。
以下ソースコード

class Decipherability {
public:
    string check(string s, int K) {
        int n = s.size();
        if (n == K) return "Certain";
        vector<int> pos[26];
        for (int i = 0; i < n; i++) pos[s[i]-'a'].push_back(i);
        for (int i = 0; i < 26; i++) {
            int m = pos[i].size();
            for (int j = 0; j < m-1; j++) {
                if (pos[i][j+1]-pos[i][j] <= K) return "Uncertain";
            }
        }
        return "Certain";
    }
};