Codeforces Round #147 Build String

問題概要

文字列tとn個の文字列s₁, s₂, ...., s_nが与えられる。sを用いてtを作る。一回の操作で

1. s₁, s₂, ...., s_nの中から任意の文字列を一つを選ぶ。
2. 1.で選んだ文字列から任意の一文字を選び、紙に書く。
3. 選んだ文字列から選んだ文字を消去する。

この操作を複数回行い、紙に書かれた文字列がtと等しくなるようにする。ただし、それぞれのs_i, i = 1,2, ..., nについて使用できる回数が決まっている。i番目の文字列を使用するとコストがiかかる。tを作るために必要な最小コストを求めよ。

方針

最小費用流を使う。
乱択を使った解法でシステムテスト通過している人がいて、おもしろいなぁと思って同じようなことやってみたけど、以下のケースで落とせるじゃん。。ただ、この考え方は覚えておいて損は無さそうだ。

abcdefghijklmnopqrstuvwxyz        
26
abcdefghijklmnopqrstuvwxyz 1
abcdefghijklmnopqrstuvwxy  1
abcdefghijklmnopqrstuvwx   1
abcdefghijklmnopqrstuvw    1
abcdefghijklmnopqrstuv     1
abcdefghijklmnopqrstu      1
abcdefghijklmnopqrst       1
abcdefghijklmnopqrs        1
abcdefghijklmnopqr         1
abcdefghijklmnopq          1
abcdefghijklmnop           1
abcdefghijklmno            1
abcdefghijklmn             1
abcdefghijklm              1
abcdefghijkl               1
abcdefghijk                1
abcdefghij                 1
abcdefghi                  1
abcdefgh                   1
abcdefg                    1
abcdef                     1
abcde                      1
abcd                       1
abc                        1
ab                         1
a                          1

ソースコード

上が最小費用流を使った解法、下が乱択を使った解法。

using namespace std;

int V;
int main()
{
    string tar;
    int n;

    cin >> tar >> n;
    vector strs(n);
    vector caps(n);

    REP(i, n) 
        cin >> strs[i] >> caps[i];

    V = 1 + n + 26 + 1;
    REP (i, n) {
        add_edge(0, 1+i, caps[i], 0);
        REP (j, 26) {
            int cnt = count(strs[i].begin(), strs[i].end(), (char)(j+'a'));
            if (cnt)
                add_edge(1+i, 1+n+j, cnt, i+1);
        }
    }

    REP (i, 26) {
        int cnt = count(tar.begin(), tar.end(), (char)(i+'a'));
        if (cnt)
            add_edge(1+n+i, 1+n+26, cnt, 0);
    }

    cout << min_cost_flow(0, 1+n+26, tar.length()) << endl;

    return 0;
}

const int INF = 1<<30;
string tar;
int n;
vector strs;
vector caps;
vector pri;

int calc(vector &x, vector &y, char c) {
    REP (i, n) { 
        if (y[i] == 0) 
            continue;
        REP (j, x[i].length()) {
            if (x[i][j] == c) {
                x[i][j] = ' ';
                y[i]--;
                return i+1;
            }
        }
    }
    return INF;
}

int main() {
    cin >> tar >> n;
    strs.assign(n, "");
    caps.assign(n, 0);
    pri.assign(tar.length(), 0);

    REP(i, n)
        cin >> strs[i] >> caps[i];
    REP(i, tar.length())
        pri[i] = i;
    
    int ret = INF;
    while (clock() < 1.8*CLOCKS_PER_SEC) {
        random_shuffle(pri.begin(), pri.end());

        vector _strs = strs;
        vector _caps = caps;

        int total = 0;
        REP (k, tar.length()) {
            char c = tar[pri[k]];
            
            int cost = calc(_strs, _caps, c);
            if (cost == INF) {
                total = INF;
                break;
            } else {
                total += cost;
            }
        }
        ret = min(ret, total);
    }

    if (ret == INF) 
        cout << -1 << endl;
    else
        cout << ret << endl;

    return 0;
}