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; }