第4回 ドワンゴからの挑戦状 本選(オープン) 問題C

競プロにちょっと興味を持った。

最速が出たので解説します。

dwacon2018-final-open.contest.atcoder.jp

(0ベースで)上からi段, 左からj番目のブロックの数字を  a _ {i,j} とする。

                   +-----+
                   | a00 | 
             +-----+-----+-----+
             | a10 | a11 | a12 |
       +-----+-----+-----+-----+-----+
       | a20 | a21 | a22 | a23 | a24 |
 +-----+-----+-----+-----+-----+-----+-----+
 | a30 | a31 | a32 | a33 | a34 | a35 | a36 |
 +-----+-----+-----+-----+-----+-----+-----+

ここで、xor を\oplusで表すと、頂点の数字は、


a _ {0,0}= a _ {1,0} \oplus  a _ {1,1}  \oplus  a _ {1,2}


\;\;
= (a _ {2,0} \oplus a _ {2,1} \oplus a _ {2,2}) \oplus
  (a _ {2,1} \oplus a _ {2,2} \oplus a _ {2,3}) \oplus
  (a _ {2,2} \oplus a _ {2,3} \oplus a _ {2,4})

のように展開していくことができる。 i回展開すると頂点の数字  a _ {0,0}  a _ {i,0}, \cdots, a _ {i,2i} によって表される。

xor 演算は結合的かつ交換的なので、 i回展開した式に a _ {i,j} が現れる回数を  n _ {i,j} で表すと、

\displaystyle
  a _ {0,0} = \bigoplus _ {j=0} ^ {2i} \bigoplus _ {n=1} ^ {n _ {i,j}} a _ {i, j}

となるが、 a \oplus a = 0 なので、   t _ {i,j} := {n _ {i,j}\, \mathrm{mod\,} 2} とすれば、

 \displaystyle
  a _ {0,0} = \bigoplus _ {j=0} ^ {2(N-1)} a _ {N-1, j} t _ {N-1,j}
  \;\; = \bigoplus _ {m=1} ^ {M} \bigoplus _ {j=P _ {m-1}} ^ {P _ {m}-1} v _ {m} t _ {N-1,j}
  \;\; = \bigoplus _ {m=1} ^ {M}  v _ {m} \left( \bigoplus _ {j=P _ {m-1}} ^ {P _ {m}-1} t _ {N-1,j} \right)

となる。ただし、 P _ {m} = L _ {1} + \cdots + L _ {m} である。

よって、 
R _ {m} := \bigoplus _ {j=P _ {m-1}} ^ {P _ {m}-1} t _ {N-1,j}
とすれば、  a _ {0,0} = \bigoplus _ {m=1} ^ M (v _ {m} R _ {m}) となり、  R _ {m} は0 または1 なので、 m = 1,…,M について、R _ {m} が1となる全ての  v _ {m} のxor を取れば良い。

 S _ {i, p} := \bigoplus _ {j=0} ^ {p} t _ {i,j} とすれば、  R _ {m} = S _ {P _ {N-1, m} - 1} - S _ {P _ {N-1, m - 1} - 1} なので、以下では、 S _ {i, j} を求める。

 t _ {i, j} の漸化式

 a _ {i,j} は、  a _ {i-1,j-2}, a _ {i-1,j-1}, a _ {i-1,j} に現れるため、  n _ {i,j} = n _ {i-1,j-2} + n _ {i-1,j-1} + n _ {i-1,j} となるため、


t _ {i,j}
= n _ {i,j} \, \mathrm{mod} \, 2
= ( n _ {i-1,j-2} + n _ {i-1,j-1} + n _ {i-1,j} ) \, \mathrm{mod} \, 2
= t _ {i-1,j-2} \oplus t _ {i-1,j-1} \oplus t _ {i-1,j}

という漸化式が得られる。

この漸化式を使ったDPによって、  2N^{2} 個のブロックを上から順に t _ {i,j} の値で埋めていくことができるが、  N \leq 252,525 \times 10^{9} なので間に合わない1

そこで、 t _ {i,j}フラクタル的な性質を用いる。

フラクタルを用いた漸化式

 t _ {i,j} を埋めていくと、 シェルピンスキーのギャスケット のようなフラクタル図形が現れる。

f:id:nunuki:20180224195259p:plain

図の全体を半分のサイズに縮小すると、上半分の図形とほぼ重なる。

実際、


t _ {2i, 2j}
= t _ {2i - 1, 2j-2} \oplus t _ {2i - 1, 2j-1} \oplus t _ {2i - 1, 2j}
= t _ {2(i-1), 2(j-2)} \oplus t _ {2(i-1), 2(j-1)} \oplus t _ {2(i-1), 2j}

となり、t _ {2i, 2j}t _ {i, j} と同じ漸化式を満たすため、 t _ {2i, 2j} = t _ {i, j} である。

また、 t _ {2i, 2j+1} = 0 である。 これは、次のように示せる:

 n _ {i,j} は、 0段,0番のブロックから、左下、下、右下のいずれかに進むという操作を繰り返し、 i段,j番のブロックにたどり着く経路の本数を表す。 各経路は、進む方向 {'l' (左下), 'r' (右下), 'c' (下)} を順に並べた文字列と一対一に対応する。 (i,j)にたどり着くためには、右下に進む回数と左下に進む回数の差が j-i に等しければよいため、 対応する文字列の文字'r'の個数と'l'の個数の差はj-i である。 iが偶数、jが奇数であるとき、文字列に含まれる'c'の個数は奇数となるため、 文字列の前半に含まれる'c'の個数と後半に含まれる'c'の個数は異なる。 このため、任意の文字列sに、sを反転させた文字列s'を対応させると、 s' はs と異なる経路に対応する。 よって、全ての文字列sには対応する文字列s' が存在するため、 文字列の個数 n _ {i,j}は偶数となり、 t _ {i, j} =  n _ {i,j}\, \mathrm{mod}\, 2 = 0である。

まとめると、i が偶数のとき、次のような漸化式が得られる。


t _ {i,j} =
  \begin{cases}
    t _ {i/2, j/2}, \;\; j: \; \mathrm{even}, \\
    0, \;\; \;\; \;\; \;\; j: \; \mathrm{odd}.
  \end{cases}

 S _ {i, j} の漸化式

i が偶数のとき、

 \displaystyle
  S _ {i, j}
  = \bigoplus _ {k=0} ^ {j} t _ {i,k}
  = \bigoplus _ {\substack{k=0 \\ k : \mathrm{even}}} ^ {j} t _ {i/2,k/2}
  = \bigoplus _ {k=0} ^ {\lfloor j/2 \rfloor} t _ {i/2,k}
  = S _ {i/2, \lfloor j/2 \rfloor}

i が奇数のとき、

 \displaystyle
  S _ {i, j}
  = \bigoplus _ {k=0} ^ {j} t _ {i,k}
  = \bigoplus _ {k=0} ^ {j} (t _ {i-1,j-2} \oplus t _ {i-1,j-1} \oplus t _ {i-1,j}) \\ \displaystyle
  = S _ {i-1,j-2} \oplus S _ {i-1,j-1} \oplus S _ {i-1,j} \\ \displaystyle
  = S _ {(i-1)/2,\lfloor (j-2)/2 \rfloor}
  \oplus S _ {(i-1)/2,\lfloor (j-1)/2 \rfloor}
  \oplus S _ {(i-1)/2,\lfloor j/2 \rfloor} \\ \displaystyle
  = \begin{cases}
      S _ {(i-1)/2,\lfloor j/2 \rfloor - 1}, \;\; j: \mathrm{odd}, \\
      S _ {(i-1)/2,\lfloor j/2 \rfloor}, \;\;\;\; j: \mathrm{even}.
    \end{cases}

まとめると、任意のi,j について、

 \displaystyle
  S _ {i, j}
  = \begin{cases}
      S _ {\lfloor i/2 \rfloor, \lfloor j/2 \rfloor - 1}, \;\; ij: \mathrm{odd}, \\
      S _ {\lfloor i/2 \rfloor, \lfloor j/2 \rfloor}, \;\;\;\; \mathrm{otherwise}.
    \end{cases}

この漸化式を使うことで、  S _ {N-1, j}再帰的に \mathcal{O} (\log N ) で計算できる。

よって、全体の計算量は  \mathcal{O} (M \log N )

実装は以下。

dwacon2018-final-open.contest.atcoder.jp

#include <vector>
#include <iostream>
using namespace std;
 
#define LL long long
 
inline LL S(LL p, LL q){
  while(true){
    if(q<0) return 0;
    if(p==0) return 1;
    q = (q>>1) - (p&q&1);
    p = p>>1;
  }
}
 
void solve(long long M, vector<long long> v, vector<long long> L){
  LL N = 0;
  for(LL m=0; m<M; m++) N += L[m];
  LL p=(N-1)>>1;
 
  LL rst=0, q=-1, prevS=S(p, q);
  for(LL m=0; m<M; m++){
    q += L[m];
    LL nextS = S(p, q);
    if(nextS != prevS) rst ^= v[m];
    prevS = nextS;
  }
  cout << rst << endl;
}
 
int main(){ 
    long long M;
    scanf("%lld",&M);
    vector<long long> L(M-1+1);
    vector<long long> v(M-1+1);
    for(LL i = 0 ; i <= M-1 ; i++){
        scanf("%lld",&v[i]);
        scanf("%lld",&L[i]);
    }
    solve(M, v, L);
    return 0;
}

  1. 実は、これでも頑張れば間に合うらしい: kmyk 氏の解答