SRM724 Lv1 : OrAndSum
作成日：2017.11.29
最終更新日：2017.11.29
問題概要
$n$個の要素からなる$pairOr$と$pairSum$が与えられる。
$(n+1)$項からなる数列$\{x\}$で、$pairOr[i]$$= x_i$$\:or\:$$x_{i+1}$、$pairSum[i]$$= x_i$$+ x_{i+1}$となるものが存在するかを判定せよ。
制約
$1 \leq n \leq 50$
$0 \leq pairOr[i] , pairSum[i] \leq 10^{18}$
考え方
数列$\{x\}$としてあり得るものを先頭から決めていくことを考える。
その際に隣接する項の$or$が与えられていることから、各bitごとに見ていけば良い。
bitごとに$0$、$1$、不定のいずれであるかを決めていき矛盾が生じたら不可能だと判定できる。
また、bitごとに見ていく時に繰り上がりがあるかどうかの情報も持たなければならない。
この情報は、ある、ない、不定の3通りを持ちうる。
$x_0$の各bitは不定であるとして、$x_i$の各bitを$(i \geq 1)$以降を$pairOr$、$pairSum$、$x_{i-1}$の各bit及び繰り上がりの有無の$36$通りの場合分けで定めれば良い。
ちなみに、$a + b$$= (a \: and \: b)$$+ (a \: or \: b)$が成り立つことを使うとより簡単になる。
ソースコード
マクロ等はこちら
const int MC = 62;
const string NG = "Impossible";
class OrAndSum {
int z[55][MC];
public:
string isPossible(vector<long long> pairOr, vector<long long> pairSum) {
int n = pairOr.size();
fill(z[0],z[0]+MC,-1);
repp(i,0,n){
fill(z[i+1],z[i+1]+MC,-1);
LL x = pairOr[i] , y = pairSum[i];
int b = 0;
repp(j,0,MC){
if(!(x&1) && !(y&1)){
if(b==1 || z[i][j]==1) return NG;
if(b<0) z[i+1][j-1] = 0;
z[i+1][j] = 0;
b = 0;
} else if(!(x&1) && (y&1)){
if(b==0 || z[i][j]==1) return NG;
if(b<0) z[i+1][j-1] = 1;
z[i+1][j] = 0;
b = 0;
} else if(!(y&1)){
if(b==0){
if(z[i][j]==0) return NG;
z[i+1][j] = 1;
b = 1;
} else if(b==1){
if(z[i][j]>=0) z[i+1][j] = 1-z[i][j];
b = 1;
} else {
if(z[i][j]==0) z[i+1][j] = 1;
b = 1;
}
} else {
if(b==0){
if(z[i][j]>=0) z[i+1][j] = 1-z[i][j];
b = 0;
} else if(b==1){
z[i+1][j] = z[i][j];
b = z[i][j];
}
}
x >>= 1;
y >>= 1;
}
}
return "Possible";
}
};解法まとめ
数列$\{x\}$を先頭からbitごとに決めていく。
その際に繰り上がりの有無を持っておく必要があることに注意する。(9-50行)
SRM724の他の問題 Lv2 Lv3