kojingharangの日記

お誕生日コンテスト E. 排他的☆論理和っ！！

18:49 |

• (概要) T個のA[i]^B[i]を求める問題。ただし問題は謎のバイナリファイルで与えられる。
• http://birthday0410.contest.atcoder.jp/tasks/birthday0410_e

• とりあえず hexdump で見てみる
• 0x70 は位置的にスペースっぽい
• 0x5a は位置的に LF っぽい
• {0x30, -0x50} を繰り返し足してくとそれっぽい？→微妙におかしい

• ...

• 加算じゃなくて XOR を使うのか
• 長さLの鍵を、復号すると数字かスペースかLFになるように求める。→ sample 0, 1 はいいけど残りは複数通りある
• まさか探索すんのか( ﾟдﾟ) そんなつもりでは
• 先頭 N バイトまでに関して、validな問題文かどうかを判定するルーチンを書いて枝刈り

• 書いてコピペ
• 書いたけど最後の１個だけ間違ってるようだ。
• ずっとsample10のデバッグしてるけど特におかしくない

• (あとで)

• atcoderの結果は順番がランダムに並び替わってるのか( ﾟдﾟ)
• sample4が少し古い結果を使ってたようだ。...

• accepted

// めんどくさい
bool isNum(const string& s, int& idx, int limit, int& out) {
	if(idx>=limit) return false;
	if(!isdigit(s[idx])) return false;
	out=0;
	int read=0;
	while(idx<limit && isdigit(s[idx])) {
		out=out*10+(s[idx]-'0');
		idx++;
		read++;
	}
	if(out==0 && read>1) return false;
	return true;
}

string realAns;
// めんどくさい
bool valid2(const string& s, int limit, bool final=false) {
	int idx=0;
	int v;
	if(idx>=limit) return !final;
	if(!isNum(s, idx, limit, v)) return false;
	if(!(1<=v&&v<=200)) return false;
	if(idx>=limit) return !final;
	if(s[idx++]!=0x0a) return false;
	int loop = v;
	stringstream ans;
	REP(i, loop) {
		int a, b;
		if(idx>=limit) return !final;
		if(!isNum(s, idx, limit, v)) return false;
		if(!(1<=v&&v<=10)) return false;
		if(idx>=limit) return !final;
		if(s[idx++]!=' ') return false;
		a=v;
		
		if(idx>=limit) return !final;
		if(!isNum(s, idx, limit, v)) return false;
		if(!(1<=v&&v<=10)) return false;
		if(idx>=limit) return !final;
		if(s[idx++]!=0x0a) return false;
		b=v;
		ans<<"ans.PB("<<(a^b)<<");";
	}
	if(final && idx!=limit) return false;
	if(final) realAns = ans.str();
	return true;
}


VVI w;
string src, validAns;
int cur[128];
int L=128;
VVI ans;
void dfs(int idx) {
	if(validAns.size()) return;
	if(idx==ans.size()) {
		string ss=src;
		REP(j, ss.size()) ss[j]^=ans[j%L][cur[j%L]];
		if(valid2(ss, ss.size(), true)) {
			cout<<"//Found valid ans "<<endl;
			validAns=ss;
		}
		return;
	}
	REP(i, ans[idx].size()) {
		cur[idx]=i;
		bool go=true;
		{
			string ss=src;
			REP(j, ss.size()) ss[j]^=ans[j%L][cur[j%L]];
			if(!valid2(ss, idx+1)) go=false;
		}
		if(go) dfs(idx+1);
	}
}

bool validChars(const VI& s) {
	int cnt=0;
	REP(i, s.size()) {
		if(isdigit(s[i]) || s[i]==' ' || s[i]==0x0a) cnt++;
	}
	return cnt==s.size();
}

int main(int argc, char**argv) {
	//ios::sync_with_stdio(false);
	int c;
	string s;
	int co=0;
	FILE* fin = fopen(argv[1], "rb");
	w = VVI(L, VI());
	while((c=fgetc(fin))!=EOF) {
		w[co%L].PB(c);
		s.PB(c);
		co++;
	}
	src=s;
	ans = VVI(L, VI());
	REP(l, L) {
		REP(a, 256) {
			VI ss=w[l];
			REP(i, ss.size()) ss[i] = (ss[i] ^ a) & 0xFF;
			if(validChars(ss)) ans[l].PB(a);
		}
	}
	dfs(0);
	
	cout<<realAns<<endl;
	
	return 0;
}

ツイートする