TopCoder SRM 724 Div1 Easy OrAndSum、Div2 OrAndSumEasy

Mediumが詰め切れなかったが、Easyがそこそこの時間で解けたのでレート微増。
https://community.topcoder.com/stat?c=problem_statement&pm=14744
https://community.topcoder.com/stat?c=problem_statement&pm=14745

問題

N+1要素の数列X[i]があったとする。
隣接要素のorおよび加算で生成されるN要素の２つの数列が与えられる。

• pairOr[i] = X[i] or X[i+1]
• pairSum[i] = X[i] + X[i+1]

pairOrとpairSumが与えられたとき、両者を満たすXが存在するかどうか判定せよ。

解法

下のビットから順に見ていこう。
最下位ビットだけに注目すると、sumとxorは実質同じである。
隣接要素のxorがわかれば、X[0]の最下位ビットを決めるとX[1]、X[2]…と順次決まる。
よってX[0]の最下位ビットを0,1両方総当たりし、pairOrと一致するか判定するとよい。
後は同じ要領で下のビットから順に決めていこう。

なお、pairOr[i]=1、pairSum[i]=1の場合、X[0]が0でも1でも成立するが問題ない。

class OrAndSum {
	public:
	string isPossible(vector<long long> pairOr, vector<long long> pairSum) {
		int N=pairSum.size();
		int i,j,k;
		
		for(i=0;i<=60;i++) {
			FOR(j,2) {
				int prev=j;
				FOR(k,N) {
					int cur=prev^(pairSum[k]&1);
					if((cur|prev)!=(pairOr[k]&1)) break;
					prev=cur;
				}
				if(k==N) {
					prev=j;
					FOR(k,N) {
						int cur=prev^(pairSum[k]&1);
						pairOr[k]>>=1;
						pairSum[k]-=prev+cur;
						pairSum[k]>>=1;
						prev=cur;
					}
					break;
				}
			}
			if(j==2) return "Impossible";
		}
		
		return "Possible";
		
		
	}
}

まとめ

自分はsumをxorとみなしたけど、sumとorからandを求めた人も多かったみたいね。