hogecoder

tsutaj 競技プログラミングの記録

TopCoder SRM 724 Div1 Easy: OrAndSum

するめうめ

tsutaj.hatenablog.com

問題概要

原文 → TopCoder Statistics - Problem Statement

ともに長さが  N の数列  \mathrm{pairOr},  \mathrm{pairSum} が与えられる。以下の条件を満たす長さ  N+1 の数列  X が構成できるかを判定せよ。

  •  X_{i}\ \  \mathrm{OR} \ \  X_{i+1} = \mathrm{pairOr}_{i} \ \ (1 \leq i \leq N)
  •  X_{i} + X_{i+1} = \mathrm{pairSum}_{i} \ \ (1 \leq i \leq N)

解説

まず、任意の非負整数  A, B に対して、  \left( A \ \  \mathrm{OR} \ \ B \right) + \left( A \ \  \mathrm{AND} \ \  B \right) = \left( A+B \right) が成立します (これは  A, B 2 進表記するとわかります)。よって、 \mathrm{pairOr} \mathrm{pairSum} の値から、  \mathrm{pairAnd} という値が求められます。

 \mathrm{pairAnd}_{i} \mathrm{pairOr}_{i} という値は、  X_{i} X_{i+1} \mathrm{AND} \mathrm{OR} をとったものですから、これらの値の  k ビット目が立っているかどうかを見ることで、次のことが分かります。

  •  \mathrm{pairOr}_{i} k ビット目が立っている →  X_{i}, X_{i+1} のどちらかで  k ビット目が立つ
  •  \mathrm{pairAnd}_{i} k ビット目が立っている →  X_{i}, X_{i+1} ともに  k ビット目が立つ
  • どちらも該当しない →  X_{i}, X_{i+1} ともに  k ビット目が立っていない

よって、最初の要素の  k ビット目を決定することによって、全ての要素の  k ビット目が何であるべきかがわかります。

したがって 「 k ビット目に対して、最初の要素を  0 または  1 にし、以降矛盾が起こらないか確かめる」という処理を全ての  k に対して行うことで解くことができます。ビットごとに独立に処理できるところに気付けるかが分かれ目な気がします。

class OrAndSum {
    public:
    string isPossible(vector<long long> pairOr, vector<long long> pairSum) {
        int N = pairOr.size();
        vector<long long> pairAnd(N);
        for(int i=0; i<N; i++) {
            if(pairSum[i] < pairOr[i]) return "Impossible";
            pairAnd[i] = pairSum[i] - pairOr[i];
            if((pairOr[i] | pairAnd[i]) != pairOr[i]) return "Impossible";
        }

        for(int b=0; b<=60; b++) {
            bool exist = false;
            for(int x=0; x<2; x++) {
                int cur = x;
                bool ok = true;
                for(int i=0; i<N; i++) {
                    int bit_cnt = 0;
                    if(pairOr[i]  >> b & 1) bit_cnt = 1;
                    if(pairAnd[i] >> b & 1) bit_cnt = 2;

                    if(bit_cnt == 2) {
                        if(cur == 0) ok = false;
                        cur = 1;
                    }
                    if(bit_cnt == 1) {
                        cur ^= 1;
                    }
                    if(bit_cnt == 0) {
                        if(cur == 1) ok = false;
                        cur = 0;
                    }
                }
                if(ok) exist = true;
            }
            if(!exist) return "Impossible";
        }
        return "Possible";
    }
};