スポンサーサイト

上記の広告は1ヶ月以上更新のないブログに表示されています。
新しい記事を書く事で広告が消せます。

Facebook Hacker Cup 2013 Round 1 B : Security

{a, b, c, d, e, f, ?} からなる長さ L の文字列 k1, k2 が与えられる。

次の条件をみたす長さ L の文字列 k のうち、辞書順最小のものを求めよ。
・ k1 の ? をそれぞれ {a, b, c, d, e, f} のいずれかに置換すると、k に一致する
・ k2 の ? をそれぞれ {a, b, c, d, e, f} のいずれかに置換すると、k を m 個の部分文字列に等分割して適当に permute したものに一致する

・ 1 ≦ L ≦ 100
・ 1 ≦ m ≦ 50
・ m は L の約数

解答

辞書順最小なので、いつもの典型パターンに持ち込む。( たとえば SRM 527 Div.1 Medium : P8XMatrixRecovery などを参照 )

k1 の先頭から順番に ? を一つずつ決め打ちしていく。
k1 の ? に適当なアルファベットを代入したとき、条件を満たす k が存在するかどうかの判定は、
・ k1 を m 等分割した部分文字列を左の頂点
・ k2 を m 等分割した部分文字列を右の頂点
・ 「k2 の部分文字列の ? をうまく定めれば k1 の部分文字列に一致させられる」という関係で辺を張る
としてできる二部グラフが完全マッチングをもつかを見ればよい。

ソースコード

#include<cstdio>
#include<vector>
#include<cassert>
#include<cstring>

#define rep(i,n) for(int i=0;i<(n);i++)

using namespace std;

const int V_MAX=50;

bool augment(int u,bool *vis,int match[2][V_MAX],const vector<int> *G){
if(u==-1) return true;

rep(i,G[u].size()){
int v=G[u][i];
if(!vis[v]){
vis[v]=true;
if(augment(match[1][v],vis,match,G)){
match[0][u]=v;
match[1][v]=u;
return true;
}
}
}
return false;
}

int bipartite_matching(int L,int R,const vector<int> *G){
static int match[2][V_MAX];
rep(u,L) match[0][u]=-1;
rep(v,R) match[1][v]=-1;

int res=0;
static bool vis[V_MAX];
rep(u,L){
rep(v,R) vis[v]=false;
if(augment(u,vis,match,G)) res++;
}
return res;
}

int m,len;
char key1[128],key2[128];

bool check(){
vector<int> G[V_MAX];
rep(u,m) rep(v,m) {
bool ok=true;
rep(i,len/m){
if(key1[len/m*u+i]!='?'
&& key2[len/m*v+i]!='?'
&& key1[len/m*u+i]!=key2[len/m*v+i]){ ok=false; break; }
}
if(ok) G[u].push_back(v);
}
return bipartite_matching(m,m,G)==m;
}

void solve(){
scanf("%d%s%s",&m,key1,key2);
len=strlen(key1);

if(!check()){
puts("IMPOSSIBLE");
return;
}

rep(i,len) if(key1[i]=='?') {
char c;
for(c='a';c<='f';c++){
key1[i]=c;
if(check()) break;
}
assert(c<='f');
}
puts(key1);
}

int main(){
int T,t; scanf("%d",&T);
for(t=1;t<=T;t++) printf("Case #%d: ",t), solve();
return 0;
}

スポンサーサイト

コメントの投稿

非公開コメント

プロフィール

fura2

Author : fura2
数学・コンピュータを中心に、考えたこと・やったことを書いていきます。

誤植等を含め、間違いはご指摘いただければ幸いです。

FC2カウンター
検索フォーム
最新記事
最新コメント
最新トラックバック
月別アーカイブ
リンク
RSSリンクの表示
上記広告は1ヶ月以上更新のないブログに表示されています。新しい記事を書くことで広告を消せます。