SRM576 Div2 Hard "CharacterBoard2"
問題
http://community.topcoder.com/stat?c=problem_statement&pm=12506
訳
マナオは行数が10000、 列数がWの行列を持っていた。
彼は、この行列を文字で埋める為、そのためのアルゴリズムを開発した。
まず始めに、長さがWを超えないような、文字列Sを選ぶ。
このSはジェネレーターと呼ばれる。
それから、次のような擬似コードで表現されるアルゴリズムで
文字を行列に埋めていく。
cur := 0 for i := 0 to 9999 for j := 0 to W - 1 X[i][j] := S.charAt(cur) cur := (cur + 1) mod length(S)
マナオは最近、メモ書きされた行列Xを発見した。
彼は、それがジェネレーターで生成されたものなのかを知りたがっている。
あなたには以下のような情報が与えられる。
String[] fragment ... これはXの一部を表した行列である。
int W ... これは行列Xの幅(列数)である。
int i0とint j0 ... これはfragmentの左上の座標である。
言い換えれば、fragment[i][j] = X[i + i0][j + j0]である。
fragmentを含んだ行列Xを生成できるジェネレーターが
何種類あるのかを返せ。
制約
fragmentの行数をN 列数をMとする。
1 <= N, M <= 10
M <= W <= 10000
考えた事
まずジェネレーターSの文字数を決めちゃう。
そうすると、fragmentの各文字が、
Sのどの場所の文字なのかが分かるので、
その場所と文字を記憶していく。
ある場所にある文字を記憶するときに、
同じ場所に既に何らかの文字が記憶されていて、それが違う文字だったら、
現在調べている文字数のジェネレーターでは、行列Xは生成できないことになる。
全てのfragmentを調べたときに、まったく記憶されていない場所は、
a~zのどれでも使えるため、* 26通りになる。
事後
fragmentが10 * 10で、Wが10000までだから
計算量は100万なのかなぁ
その割には時間かかっていたような気がする。
ソースコード
char S[10050]; const int MOD = 1000000009; class CharacterBoard2 { public: int countGenerators(vector <string> fragment, int W, int i0, int j0){ int h = fragment.size(); int w = fragment[0].length(); long long res = 0; // ジェネレーターSの文字数lenを決める for( int len = 1; len <= W; len++ ){ // 全部?にしとく for( int i = 0; i < len; i++ ) S[i] = '?'; bool ok = true; for( int i = 0; i < h; i++ ){ int base = (i0+i) * W; for( int j = 0; j < w; j++ ){ int index = (base + j0 + j) % len; // 既に違う文字が入ってたらダメ if( S[index] != '?' && S[index] != fragment[i][j] ){ ok = false; break; } S[index] = fragment[i][j]; } } if( ok ){ long long lenRes = 1; for( int i = 0; i < len; i++ ){ // 何にも入ってないところの数だけ*26する if( S[i] == '?' ){ lenRes = lenRes * 26 % MOD; } } res = (res + lenRes) % MOD; } } return (int)res; } };