Google Code Jam Japan 2011 本戦 C. ワイルドカード(small)

C : ワイルドカード

• 本戦では、なぜかlarge行ける！と思ってしばらくハマってた問題
  • 「AにマッチするがBにマッチしない」という文面に気付くまで1時間かかった(´；ω；｀)

• largeを捨ててしまえば、smallは全探索で良い
  • Aの文字を"*"で置き換えて、連続する"*"を1個の"*"で置き換えると1つのパターンに
  • smallなら最大で2^10個のパターンを試すだけで済む

• C++では正規表現が使えなくも無いですが、面倒なので頑張って実装しました
  • 正規表現が使えるらしいJavaでも書いてみたらだいぶ簡潔に
  • この問題セット的にC++はオワコn…いや、何でもないです

書いてみたコードたち

• C++版

#include <iostream>
#include <string>

using namespace std;

string comp(string a, string b){
    if(a.size() != b.size())
        return a.size() < b.size() ? a : b;
    int cntA = 0, cntB = 0;
    for(int i=0;i<a.size();i++) if(a[i]=='*') cntA++;
    for(int i=0;i<b.size();i++) if(b[i]=='*') cntB++;
    if(cntA != cntB)
        return cntA < cntB ? a : b;
    return a < b ? a : b;
}

bool check(string a, string b){
    bool ok[51][51];
    memset(ok, false, sizeof(ok));
    ok[0][0] = true;
    for(int i=0;i<a.size();i++){
        for(int j=0;j<b.size();j++){
            if(!ok[i][j]) continue;
            if(a[i]=='*'){
                ok[i+1][j] = ok[i][j+1] = ok[i+1][j+1] = true;
            } else {
                if(a[i]==b[j]) ok[i+1][j+1] = true;
            }
        }
        if(a[i]=='*' && ok[i][b.size()]) ok[i+1][b.size()] = true;
    }
    return !ok[a.size()][b.size()];
}

string solveSmall(string a, string b){
    int n = a.size();
    string res = a;
    for(int i=0;i<(1<<n);i++){
        string cur = "";
        bool ok = false;
        for(int j=0;j<n; ){
            if(!(i&(1<<j))){
                if(j==0 || (i&(1<<(j-1)))) cur += "*";
                j++;
                continue;
            }
            string tmp = "";
            while(j<n && (i&(1<<j))) tmp += a[j++];
            cur += tmp;
        }
        if(check(cur, b)) res = comp(res, cur);
    }
    return res;
}

int main(){
    int TEST; cin >> TEST;
    for(int test=1;test<=TEST;test++){
        string a, b; cin >> a >> b;
        printf("Case #%d: %s\n", test, solveSmall(a, b).c_str());
    }
}

• Java版

import java.util.*;
import java.math.*;

public class C{
    private static String checkStr(String A, String B){
        if(A.length() != B.length())
            return A.length() < B.length() ? A : B;
        int countA = 0, countB = 0;
        for(int i=0;i<A.length();i++)
            if(A.charAt(i) == '*') countA++;
        for(int i=0;i<B.length();i++)
            if(B.charAt(i) == '*') countB++;
        if(countA != countB)
            return countA < countB ? A : B;
        return A.compareTo(B) < 0 ? A : B;
    }
    private static String solveSmall(String A, String B){
        int n = A.length();
        String res = A;
        for(int i=0;i<(1<<n);i++){
            String cur = "";
            for(int j=0;j<n;j++){
                if((i>>j)%2 == 1) cur += A.charAt(j);
                else              cur += "*";
            }
            cur = cur.replaceAll("[*]+", "*");
            Pattern p = Pattern.compile("^" + cur.replaceAll("[*]", ".*") + "$");
            if(p.matcher(B).find() == false)
                res = checkStr(res, cur);
        }
        return res;
    }
    public static void main(String args[]){
        Scanner sc = new Scanner(System.in);
        int testNum = sc.nextInt();
        for(int i=1;i<=testNum;i++){
            String A = sc.next(), B = sc.next();
            System.out.println("Case #" + i +": " + solveSmall(A, B));
        }
    }
}