WARush

SRMの結果とか、解けた問題のコードを書いていきます

Codeforces #187 Div2 D "Sereja and Periods"

問題

http://codeforces.com/contest/315/problem/D

[x, n]の説明をする。xは文字列で、nは正の整数である。[x, n]はx + x + x + ... + xとxをn回結合するという意味である。例えば、[abc, 2]は"abcabc"となる。

もし、文字列tの文字をいくつか取り除いて文字列sにすることができれば、文字列sは文字列tから得る事ができる。例えば、" ab "や" acba "は" xacbac "から得る事ができ、" bx "や" aaa "は得る事はできない。

セレジャは 文字列 w = [a, b]、そして文字列 q = [c, d]を持っている。wから得られるような[q, p]で、最大のpを出力せよ。

制約

1 <= b, d <= 10^7
1 <= a.length() b.length() <= 100



考えた事

例)
a = "abab" c = 10
b = "bab"  d = 3
前処理

文字列 b を作るとき、文字列 a のこの部分から作ったら、いったい何文字消費しなけりゃいけないのよ!そんで次はどこから始まるのよ!という表を作る。具体的には例を参考にしてもらうと、aのindex 0 から始めたら4文字消費し、次はindex0からスタート。aのindex 1 から始めたら3文字消費し、次はindex0からスタート。aのindex 2 から始めたら4文字消費し、次はindex2からスタート。aのindex 3 から始めたら3文字消費し、次はinde2からスタート。という感じ。

答えを出す

前処理で作った表をつかって、a * c文字消費する前に、bは何個作れるのか(b_num)を出したら、答えはb_num / d。ただしa * cは最大10^9。bは最小1なので、計算量は最大で10^9 / 1 = 10^9になってしまう可能性がある。

前処理プラス

bを1個だけ作る表だけじゃ物足りない!2個先・4個先・8個先の表も作ればいいじゃない!・・・という訳で、そうゆう表を計算量がいい感じになるまで作る。計算量を10^9->10^6ぐらいにすれば余裕なので、1024(2^10)個先までの表を用意すれば十分。



ソースコード

int main() {
    // 入力
    string a, b;
    int an, bn;
    int c, d;
    cin >> c >> d;
    cin >> a >> b;
    an = a.length();
    bn = b.length();

    // 文字が全て揃ってるか確認
    for( int i = 0; i < bn; i++ ){
        bool ok = false;
        for( int j = 0; j < an; j++ ){
            if( b[i] == a[j] ) ok = true;
        }
        if( !ok ){ // 絶対ムリ
            cout << 0 << endl;
            return 0;
        }
    }
    
    // 前処理
    // need[i][j] : 
    // bを2^i個作るときindex jから始めたら、文字何個消費するか?
    int need[20][110];
    // nex[i][j] :
    // bを2^i個作るときindex jから始めたら、次はどのindexから始まるか?
    int  nex[20][110];
    for( int i = 0; i < an; i++ ){
        // 文字列を100回繋げる(100回で絶対文字列bは作れる)
        string aaaaaaaa;
        for( int j = 0; j < 100; j++ ){
            aaaaaaaa += a;
        }

        // 何個消費するか・次はどこからになるか
        int p = 0;
        for( int j = 0; j < bn; j++ ){
            while( b[j] != aaaaaaaa[p++] ){}
        }
        need[0][i] = p;
        nex[0][i] = (p + i) % an;

        // 前の文字を最後に持っていく
        char ch = a[0];
        a.erase( 0, 1 );
        a += ch;
    }
    // 2個先・4個先・8個先・・・
    for( int i = 1; i <= 10; i++ ){
        for( int j = 0; j < an; j++ ){
            need[i][j] = need[i-1][j] + need[i-1][nex[i-1][j]];
            nex[i][j] = nex[i-1][nex[i-1][j]];
        }            
    }

    // 文字列bがどんだけ作れるか計算
    int b_num = 0;    // 作れた文字列bの数
    int p = 0;        // 今文字列aのどのindexにいるか
    int rem = an * c; // 残り文字
    int chk = 10;     // 1024(2^10)個先からチェックを始める
    while( true ){
        if( need[chk][p] <= rem ){
            b_num += 1 << chk;
            rem -= need[chk][p];
            p = nex[chk][p];
        }else if( chk == 0 ){
            break;
        }else{
            chk--;
        }
    }

    // dで割ったのが答え
    cout << (b_num / d) << endl;
}