SRM572

時が流れるのは速いなあと(1個前の記事を見て)思いつつ。

• -

250. NewArenaPassword

問題：与えられた文字列を、先頭からK文字とった文字列と、後ろからK文字とった文字列が一致するように書き換えたい。最小で何文字変えれば良いか。

• 文字列長nに対してn-K文字周期の文字列になれば良いとかあった気がする。
• けど、怖いので同じ文字じゃなきゃいけない場所をUnionFindで求める。
• 同じ文字じゃないといけないグループごとに、一番多い文字に合わせれば良い。

int root[50];
int getRoot(int v) { return root[v]==-1 ? v : root[v] = getRoot(root[v]); }

class NewArenaPassword {
public:
    int minChange(string oldPassword, int K) {
        int n = oldPassword.size();
        memset(root, -1, sizeof(root));
        for(int i=0;i<K;i++){
            if(i!=n-K+i){
                int p = getRoot(i);
                int q = getRoot(n-K+i);
                if(p!=q) root[q] = p;
            }
        }
        int res = 0;
        for(int i=0;i<n;i++){
            vector<int> cnt(26, 0);
            int sum = 0, mx = 0;
            for(int j=0;j<n;j++){
                if(getRoot(j) == i){
                    sum++;
                    cnt[oldPassword[j]-'a']++;
                    mx = max(cnt[oldPassword[j]-'a'], mx);
                }
            }
            res += sum - mx;
        }
        return res;
    }
};

500. EllysBulls

問題：目標とする数字(2〜9桁)があって、(予想した数字, 合ってる桁の数)の組が最大50個与えられる。目標とする数字が一意に特定できればその数字を、候補が複数あるか、存在しなければその意を答える。

• 死ぬほど頑張って枝刈り探索すれば行ける気もしたけど思いとどまった。
• 探索勢は死屍累々だったので思いとどまって良かった。

• 怪しげな式を立てたりしながら考えてたら、半分全列挙な気がしてきた。
• 検索対象がvectorなのが不安だったけど、探索よりはマシだと思って突撃した。
• 不安とか言ってる割にstring生成しまくっててアレ。

class EllysBulls {
private:
    string itos(int a){
        ostringstream oss; oss << a;
        return oss.str();
    }
public:
    string getNumber(vector <string> guesses, vector <int> bulls) {
        string res;
        int n = bulls.size();
        int m = guesses[0].size(), m2 = (m+1)/2;
        int end = 1;
        map< vector<int>, int > mp;
        for(int i=m2;i<m;i++) end *= 10;
        for(int i=0;i<end;i++){
            string str = itos(i);
            while(str.length() < m-m2) str = "0"+str;
            bool ok = true;
            vector<int> v = bulls;
            for(int j=0;j<n;j++){
                for(int k=m2;k<m;k++){
                    if(guesses[j][k] == str[k-m2]){
                        v[j]--;
                        if(v[j] < 0) ok = false;
                    }
                    if(!ok) break;
                }
                if(!ok) break;
            }
            if(ok){
                if(mp.count(v)) mp[v] = -1;
                else            mp[v] = i;
            }
        }
        end = 1;
        for(int i=0;i<m2;i++) end *= 10;
        for(int i=0;i<end;i++){
            string str = itos(i);
            while(str.length() < m2) str = "0"+str;
            vector<int> v(n, 0);
            bool ok = true;
            for(int j=0;j<n;j++){
                for(int k=0;k<m2;k++){
                    if(guesses[j][k] == str[k]){
                        v[j]++;
                        if(v[j] > bulls[j]) ok = false;
                    }
                    if(!ok) break;
                }
                if(!ok) break;
            }
            if(ok && mp.count(v)){
                int r = mp[v];
                if(r==-1 || res != "") return "Ambiguity";
                string a = itos(i);
                while(a.size() < m2) a = "0"+a;
                string b = itos(r);
                while(b.size() < m-m2) b = "0"+b;
                res = a+b;
            }
        }
        return res == "" ? "Liar" : res;
    }
};

• -

結果：AC / AC / -- ，+0, 453.93 pt, 34位
レーティング：2266 -> 2329

500に50分近くかかっててうごご…と思ってましたが、
その前のSRMは0完だったので頑張った方な気もします。
最近、競技熱が戻りつつあるので今のうちに頑張っておきたいところ。