235.95 Failed Failed +50*0 -25*0 Total:235.95 1192→1148(-44)
三回連続で減少している。ひどい。
偶数番目にxが、もしくは奇数番目にoがある場合には、oxoxoxox...となり、そうでない場合はxoxoxoxo...となる。
//include等は省略 class NetworkXZeroOne { public: string reconstruct(string message) { int d; char a,b; for(int i=0;i<message.size();i++){ if(message[i]=='o'){ if(i%2==0){ a='o'; b='x'; }else{ a='x'; b='o'; } } else if(message[i]=='x'){ if(i%2==0){ a='x'; b='o'; }else{ a='o'; b='x'; } } } for(int i=0;i<message.size();i++){ if(i%2==0) message[i]=a; else message[i]=b; } return message; } };
単純に全探索っぽいことをしたらTLEしてしまった。
提出したコードは
//include等は省略 class NetworkXOneTimePad { public: string _xor(string a,string b){ string ret; for(int i=0;i<a.size();i++){ if(a[i]==b[i]) ret+=string(1,'0'); else ret+=string(1,'1'); } return ret; } int crack(vector <string> pl, vector <string> ci) { set<string> strs; for(int j=0;j<pl.size();j++){ for(int i=0;i<ci.size();i++){ string key=_xor(ci[i],pl[j]); bool isok=true; for(int k=0;k<ci.size();k++){ bool is=false; for(int l=0;l<pl.size();l++){ if(_xor(pl[l],key)==ci[k]){ is=true; } } if(!is) isok=false; } if(isok) strs.insert(key); } } return strs.size(); } };
xorをstringのままシュミレートしていたところを、一旦long longに変換して、それでxorをとってやればTLEせずに通る。
//include等は省略 class NetworkXOneTimePad { public: int crack(vector <string> pl, vector <string> ci) { set<ll> keys; vector<ll> pln(pl.size()),cin(ci.size()); for(int i=0;i<pl.size();i++){ ll n=0; for(int j=0;j<pl[i].size();j++){ n+=(pl[i][j]-'0')*((ll)1<<j); } pln[i]=n; } for(int i=0;i<ci.size();i++){ ll n=0; for(int j=0;j<ci[i].size();j++){ n+=(ci[i][j]-'0')*((ll)1<<j); } cin[i]=n; } for(int j=0;j<pl.size();j++){ for(int i=0;i<ci.size();i++){ ll key=cin[i]^pln[j]; bool isok=true; for(int k=0;k<ci.size();k++){ bool is=false; for(int l=0;l<pl.size();l++){ if((pln[l]^key)==cin[k]){ // == は ^ よりも優先度が高いことに注意 is=true; } } if(!is) isok=false; } if(isok) keys.insert(key); } } return keys.size(); } };
ちなみに、上のプログラムのオーダーはO(N^4)くらいだが、二分探索などを使えばO(N^3logN)でも通る。そのプログラムは、
class NetworkXOneTimePad { public: int crack(vector <string> pl, vector <string> ci) { set<ll> strs; vector<ll> pln(pl.size()),cin(ci.size()); for(int i=0;i<pl.size();i++){ ll n=0; for(int j=0;j<pl[i].size();j++){ n+=(pl[i][j]-'0')*((ll)1<<j); } pln[i]=n; } for(int i=0;i<ci.size();i++){ ll n=0; for(int j=0;j<ci[i].size();j++){ n+=(ci[i][j]-'0')*((ll)1<<j); } cin[i]=n; } for(int j=0;j<pl.size();j++){ for(int i=0;i<ci.size();i++){ ll key=cin[i]^pln[j]; vector<ll> plci(pl.size()); for(int k=0;k<pl.size();k++){ plci[k]=pln[k]^key; } bool is=true; sort(ALL(plci)); for(int k=0;k<ci.size();k++){ if(!binary_search(ALL(plci),cin[k])) is=false; } if(is) strs.insert(key); } } return strs.size(); } };
解法が思いつかなかったので適当なアルゴリズムをでっちあげて提出する。順序が逆になってる間ずっとそれをもとに戻すようなアルゴリズム。ちゃんと辞書順になってくれないケースが存在するので通らない。
//include等は省略 class NetworkXMessageRecovery { public: string recover(vector <string> messages) { set<char> cs; set<pair<char,char> > cha; for(int i=0;i<messages.size();i++){ for(int j=0;j<messages[i].size();j++){ cs.insert(messages[i][j]); } for(int j=1;j<messages[i].size();j++){ cha.insert(make_pair(messages[i][j-1],messages[i][j])); } } string fi; for(set<char>::iterator it=cs.begin();it!=cs.end();it++){ fi+=string(1,*it); } for(;;){ bool is=false; for(set<pair<char,char> >::iterator it=cha.begin();it!=cha.end();it++){ int fst,snd; for(int i=0;i<fi.size();i++){ if(fi[i]==it->first) fst=i; if(fi[i]==it->second) snd=i; } if(fst>snd){ is=true; char t=fi[fst]; fi[fst]=fi[snd]; fi[snd]=t; } } if(!is) break; } return fi; } };
終わった後考えても分からなかったので解法を調べる。
次に取り出す文字を一回一回決めて、全部取り出したらそれを連結した文字列を返す。
その決め方：それぞれの部分文字列のまだ取り出していない文字のなかでもっとも先頭にあるもののうち、ほかの部分文字列のまだ取り出していない文字のうちの先頭以外の部分に含まれていない文字たちが次に取り出す候補となる。辞書順にしたいので、その候補のうちもっとも辞書順で小さいものが次に取り出す文字。
//include等は省略 class NetworkXMessageRecovery { public: string recover(vector <string> mes) { vector<int> pos(mes.size(),0); string ret; for(;;){ vector<char> kouho; for(int i=0;i<mes.size();i++){ if(pos[i]==mes[i].size()) continue; char nc=mes[i][pos[i]]; bool is=true; for(int j=0;j<mes.size();j++){ if(i==j) continue; for(int k=pos[j]+1;k<mes[j].size();k++){ if(mes[j][k]==nc) is=false; } } if(is) kouho.push_back(nc); } sort(ALL(kouho)); if(kouho.size()>=1){ ret+=kouho[0]; for(int i=0;i<pos.size();i++){ if(mes[i][pos[i]]==kouho[0]) pos[i]++; } }else break; } return ret; } };
なにもできない、なにもされない