yukicoder No.470 Inverse S+T Problem
問題概要
3つの文字でできている文字列があたえられる.それらを前後で分けて、すべての文字列が相異なるように分けられるなら分けろ。
解法
考察として、文字を分けるのは1-2または2-1の2通りしかないので、2n通りすべてを調べれば答えが求まることがわかる。また,文字が大文字小文字合わせて、26*2=52通りしかないので、n > 52の場合は条件を満たすようなことはありえない. (1文字のものはn通り現れるので、52より大きい時は無理) よって、 愚直にやると、252となり無理だ。
これ以上はわからなかった。今回は、2通りにしか分ける方法はないということで、2-SATという方法があるらしい。蟻本p288から詳しく載っている。
サンプル1:
abc
abd
cbc
の3通りの文字列があり、これを2-1または1-2に分けていく。
abcとabdを考えてみる。分け方は全部で以下の4通り。
2-1 2-1
ab c | ab d
2-1 1-2
ab c | a bd
1-2 2-1
a bc | ab d
1-2 1-2
a bc | a bd
この中で、相異なっていないものは、2-1 2-1, 1-2 2-1, 1-2 1-2, の3通りである。
ここで、i番目の文字列を2-1に分ける時をx_i(=T)として、1-2に分ける時をnotx_i(=F)とする。
例えば、上の例で2-1 2-1にわけた時、つまり、x_0(=T) x_1(=T)とした時、a V b という論理式の結果を偽とするには、
notx_0 V notx_1 とすれば、x_0とx_1が真なので、notx_0 V notx_1 (=F) となる。これは条件を満たさない時のTFをひっくり返して条件を満たさないTFになったときに、aVbの形がFとなるようにしているだけ。
よって、0番目の文字列と1番目の文字列については、
(notx_0 V notx_1) かつ (notx_0 V x_1) かつ (x_0 V x_1)
という形になる。この3つの論理式がすべてTであれば、全体としてもTとなる。これが意味するのは、0番目の文字列と1番目の文字列を相異なるようにわけられたといことである。
これを他の文字列どおりの組み合わせにおいても同じことを行いa V bの形の論理式が、かつ で結ばれた全体の論理式を作る。これが真を満たすx_iの組があれば解が存在することはわかる。
この論理式の解き方は、p V qというのを、(notp->q) かつ (notq->p) という形に書き直せることを利用して、これをImplication graphにする。
論理式の式変形等の参考サイト
ミス
2-SATを勉強する良い機会になった。なかなか気づきにくと思うけど、愚直解を考えたときに、2nとなるような場合は2-SATかもと考えれば思いつくのかな?
コード
#include <bits/stdc++.h> using namespace std; typedef long long ll; typedef vector<int> vint; typedef pair<int,int> pint; typedef vector<pint> vpint; #define rep(i,n) for(int i=0;i<(n);i++) #define reps(i,f,n) for(int i=(f);i<(n);i++) #define each(it,v) for(__typeof((v).begin()) it=(v).begin();it!=(v).end();it++) #define all(v) (v).begin(),(v).end() #define pb push_back #define mp make_pair #define fi first #define se second #define chmax(a, b) a = (((a)<(b)) ? (b) : (a)) #define chmin(a, b) a = (((a)>(b)) ? (b) : (a)) const int MOD = 1e9 + 7; const int INF = 1e9; class strongly_connected_components{ public: int group_cnt; // sccの数 vector<vector<int> > G, rG; vector<int> used, vs; vector<int> cmp; //cmp[v] := 頂点vが含まれる連結成分がどれなのかを示す番号 strongly_connected_components(const vector<vector<int> > &g, const vector<vector<int> > &rg, int n): G(g), rG(rg), cmp(2 * n), used(2 * n){ //mainの処理 fill(used.begin(), used.end(), 0); for (int i = 0; i < G.size(); ++i){ if(!used[i]) dfs(i); } fill(used.begin(), used.end(), 0); int k = 0; for (int i = vs.size() - 1; i >= 0; --i){ if(!used[vs[i]]) rdfs(vs[i], k++); } group_cnt = k; } int operator[](int i){//連結成分の番号を返す return cmp[i]; } private: void dfs(int curr){ used[curr] = true; for(auto next : G[curr]){ if(!used[next]) dfs(next); } vs.push_back(curr); } void rdfs(int curr, int k){ used[curr] = true; cmp[curr] = k;//頂点vに対して、k番目と強連結成分であること入れる for(auto next : rG[curr]){ if(!used[next]) rdfs(next, k); } } }; class twosatisfiability{ public: int V; vector<int> res; // 1:= 0:= vector<vector<int> > g, rg; twosatisfiability(int n) : V(n), g(2 * n), rg(2 * n), res(n){} bool exec() { strongly_connected_components scc(g, rg, V); for (int i = 0; i < V; i++) { if (scc[i] == scc[i + V]) return false; res[i] = scc[i] > scc[i + V]; } return true; } void add_edge(int a, int b){ g[a].push_back(b); rg[b].push_back(a); } //0~V-1: x_i //V~2V-1: notx_i void add(int a, bool apos, int b, bool bpos){//a V b をグラフへ add_edge(a + (apos ? V : 0), b + (bpos ? 0 : V)); // not a -> b add_edge(b + (bpos ? V : 0), a + (apos ? 0 : V)); // not b -> a } bool operator[](int k){ return res[k]; } }; int n; string u[100010]; int main(void){ cin >> n; rep(i, n) cin >> u[i]; if(n > 26 * 2){ printf("Impossible\n"); return 0; } twosatisfiability sat(n); rep(i, n){ reps(j, i + 1, n){ //u[i]を2,1文字に分けるとき、かつそのときに限りx_iに真を割りあてる //被りが生じるような組み合わせには偽となるような節を追加 string a = u[i]; string b = u[j]; //かぶさる可能性のあるものを反転させたものをグラフに追加する if (a.substr(0, 1) == b.substr(0, 1) || a.substr(1, 2) == b.substr(1, 2)) {// false false sat.add(i, true, j, true); } if (a.substr(0, 1) == b.substr(2, 1) || a.substr(1, 2) == b.substr(0, 2)) {//false true sat.add(i, true, j, false); } if (a.substr(0, 2) == b.substr(1, 2) || a.substr(2, 1) == b.substr(0, 1)) {//true false sat.add(i, false, j, true); } if (a.substr(0, 2) == b.substr(0, 2) || a.substr(2, 1) == b.substr(2, 1)) {//true true sat.add(i, false, j, false); } } } bool flag = sat.exec(); if(!flag){ printf("Impossible\n"); return 0; }else{ rep(i, n){ if(sat[i]){ cout << u[i].substr(0, 2) << " " << u[i].substr(2, 1) << endl; }else{ cout << u[i].substr(0, 1) << " " << u[i].substr(1, 2) << endl; } } } return 0; }