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

変わった入力の問題。
http://birthday0410.contest.atcoder.jp/tasks/birthday0410_e

問題

以下の形式を持つ入力が与えられる。

• 1行目はテストケース数T
• 2～(T+1)行目は1つのテストケースに対応しており、1～10の数値が空白区切りで2つ

各テストケースに対し、２つの数字のxorに答えよ。

ただし、入力は何らかの手段で暗号化されており、ヒントとして解読に必要な数値Lが与えられている。

解法

暗号化さえ解いてしまえば、後は簡単。頑張って暗号を解こう。

サンプルと問題タイトルから、以下のことがわかる。
暗号化前の平文文字列をバイト単位の配列P[i]、暗号化後の入力文字列をC[i]とすると、ある暗号化キーX[i]を用いて各C[i] = P[i] ^ X[i%L]の関係にある。

よって、Lバイトの暗号化キーX[i]を求めるのが問題となる。
まず以下の手順でXの候補を絞り込もう。

• 暗号化後に登場する文字は0～9かスペースか改行文字

この時点で、テストケース1,2ではXが特定できるので、部分点を得ることができる。
ただしテストケース3以降ではまだXを特定できず、候補が残るのでより絞り込みが必要。
入力形式全体を頑張ってパースしても良いが、下記のように各文字周辺を絞り込むだけでもXが特定できた。

先頭のバイトはテストケース数なので例外とするため、５バイト名以降を以下の通り残り候補のX[i]
に対して総当たりで可否判定する。

• P[i]が'0'なら、それは'10'の一部なので直前に'1'が来て、直後に空白か改行が来る。
• P[i]が'1'なら、それは'10'の一部なので直前に空白か改行が来て、直後に'0'か空白か改行が来る。
• P[i]が'2'～'9'なら、直前および直後に空白または改行が来る。
• P[i]が空白なら、直前および直後に数字が来る。また、２・３文字前後に改行文字が来る。
• P[i]が改行なら、直前および直後に数字が来る。また、２・３文字前後に空白文字が来る。

int L,F;
unsigned char hoge[1000];
int ng[200][256];
vector<int> cand[128];

int okok(int id,int val,int val2) {
	ITR(it,cand[id%L]) if((hoge[id]^*it)>=val && (hoge[id]^*it)<=val2) return 1;
	return 0;
}


void solve() {
	int f,i,j,k,l,x,y;
	
	FOR(i,F) {
		FOR(y,256) {
			x=y^hoge[i];
			if(x!=0xA && x!=0x20 && (x<'0' || x>'9')) ng[i%L][y]=1;
		}
	}
	FOR(i,L) FOR(x,256) if(ng[i][x]==0) cand[i].push_back(x);
	
	FOR(i,F) if(i>5 && i<F-1 && cand[i%L].size()>1) {
		vector<int> c2;
		ITR(it,cand[i%L]) {
			x = hoge[i] ^ *it;
			int ng=0;
			
			if(x=='0') {
				ng |= !okok(i-1,'1','1');
				ng |= !okok(i+1,' ',' ') && !okok(i+1,0xa,0xa);
			}
			else if(x=='1') {
				ng |= !okok(i-1,' ',' ') && !okok(i-1,0xa,0xa);
				ng |= !okok(i+1,'0','0') && !okok(i+1,' ',' ') && !okok(i+1,0xa,0xa);
			}
			else if(x>='2' && x<='9') {
				ng |= !okok(i-1,' ',' ') && !okok(i-1,0xa,0xa);
				ng |= !okok(i+1,' ',' ') && !okok(i+1,0xa,0xa);
			}
			else if(x==' ' || x==0xa) {
				ng |= !okok(i-1,'0','9');
				ng |= !okok(i+1,'1','9');
				if(x==' ' && i>8 && i<F-7) ng |= !okok(i-2,0xa,0xa) && !okok(i-3,0xa,0xa);
				if(x==' ' && i>8 && i<F-7) ng |= !okok(i+2,0xa,0xa) && !okok(i+3,0xa,0xa);
				if(x==0xa && i>8 && i<F-7) ng |= !okok(i-2,' ',' ') && !okok(i-3,' ',' ');
				if(x==0xa && i>8 && i<F-7) ng |= !okok(i+2,' ',' ') && !okok(i+3,' ',' ');
				
			}
			if(!ng) c2.push_back(*it);
		}
		cand[i%L]=c2;
	}
	
	ll h=1;
	FOR(i,L) h*=cand[i].size();
	if(h!=1) return;
	
	FOR(i,F) ungetc(hoge[F-1-i]^cand[(F-1-i)%L][0],stdin);
	cin>>j;
	FOR(i,j) {
		cin>>x>>y;
		_P("%d\n",x^y);
	}
}


int main(int argc,char** argv){
	L=atoi(argv[1]);
	F=0;
	int c;
	
	FILE* fp = fopen( argv[2], "r" );
	while((c=fgetc(fp))>=0) hoge[F++]=c;
	fclose(fp);
	solve();
	
	return 0;
}

まとめ

本番は枝刈りをさぼって部分点10ptどまり。
でも結局自力で解けたし、本番これ完答すればよかったな。