kojingharangの日記

Facebook Hacker Cup Round1 B - Security

19:32 |

• 長さ M のセクション L 個からなる、長さ N の文字列 K, K1, K2 のうち K1, K2 が与えられる。K は abcdef だけを含む。K1 は K の 0 文字以上が ? に置き換わっている。K2 は K のセクションの順序が適当に並び替えられた上で 0 文字以上が ? に置き換わっている。
• K としてありうる辞書順最小の文字列を求める問題。
• N≦100, M≦50

• 辞書順最小ということで、制約を満たす状態を保ったまま先頭から貪欲に決めてく。
• 制約を満たすかどうかは K1 のセクションと K2 のセクション間の２部マッチングで。といいつつSpaghetti Sourceさんのフローライブラリをぺたぺた。
• 各文字ペアのどれかが「両方 a〜f かつ文字が違う」というときだけマッチしないので辺を張らない。流量が M なら制約を満たす。

• Accepted

/////////////////////// [OPTION] maximumFlow
#define INF 1000000
typedef int Weight;
struct Edge {
  int src, dst;
  Weight weight;
  Edge(int src, int dst, Weight weight) :
    src(src), dst(dst), weight(weight) { }
};
bool operator < (const Edge &e, const Edge &f) {
  return e.weight != f.weight ? e.weight > f.weight : // !!INVERSE!!
    e.src != f.src ? e.src < f.src : e.dst < f.dst;
}
typedef vector<Edge> Edges;
typedef vector<Edges> Graph;

typedef vector<Weight> Array;
typedef vector<Array> Matrix;

#define RESIDUE(s,t) (capacity[s][t]-flow[s][t])
Weight maximumFlow(const Graph &g, int s, int t) {
  int n = g.size();
  Matrix flow(n, Array(n)), capacity(n, Array(n));
  REP(u,n) FOR(e,g[u]) capacity[e->src][e->dst] += e->weight;

  Weight total = 0;
  while (1) {
    queue<int> Q; Q.push(s);
    vector<int> prev(n, -1); prev[s] = s;
    while (!Q.empty() && prev[t] < 0) {
      int u = Q.front(); Q.pop();
      FOR(e,g[u]) if (prev[e->dst] < 0 && RESIDUE(u, e->dst) > 0) {
        prev[e->dst] = u;
        Q.push(e->dst);
      }
    }
    if (prev[t] < 0) return total; // prev[x] == -1 <=> t-side
    Weight inc = INF;
    for (int j = t; prev[j] != j; j = prev[j])
      inc = min(inc, RESIDUE(prev[j], j));
    for (int j = t; prev[j] != j; j = prev[j])
      flow[prev[j]][j] += inc, flow[j][prev[j]] -= inc;
    VI path;
    for (int j = t; prev[j] != j; j = prev[j]) path.push_back(j);
    path.push_back(s);
    reverse(ALL(path));
    total += inc;
//    cout<<"Update "<<path<<" -> total "<<total<<endl;
  }
}
void add_edge(Graph& g, int s, int e, int w) {
	g[s].push_back(Edge(s, e, w));
	g[e].push_back(Edge(e, s, 0));
}
/////////////////////// maximumFlow

ll N, M, L;
string K1, K2;

int check() {
	Graph g(M*2+2, Edges());
	int S=M*2, E=M*2+1;
	REP(i, M) {
		add_edge(g, S, i, 1);
		add_edge(g, M+i, E, 1);
	}
	// i in K1, j in K2
	REP(i, M) REP(j, M) {
		int lok=1;
		REP(li, L) {
			char a=K1[i*L+li], b=K2[j*L+li];
			if(!(a=='?' || b=='?') && a!=b) lok=0;
		}
		if(lok) add_edge(g, i, M+j, 1);
	}
	int flow = maximumFlow(g, S, E);
	return flow==M;
}

int main() {
	int T;
	cin>>T;
	REP(ttt, T) {
		cin>>M;
		cin>>K1>>K2;
		N=K1.size();
		L=N/M;
		
		int gok=1;
		REP(ci, N) {
			if(K1[ci]=='?') {
				int ok=0;
				REP(cand, 6) {
					K1[ci]=cand+'a';
					if(check()) {ok=1;break;}
				}
				if(!ok) {gok=0;break;}
			}
		}
		if(!check()) gok=0;
		
		if(gok) {
			cout<<"Case #"<<ttt+1<<": "<<K1<<endl;
		} else {
			cout<<"Case #"<<ttt+1<<": IMPOSSIBLE"<<endl;
		}
	}
	return 0;
}

ツイートする