第4回 ドワンゴからの挑戦状 本選(オープン) 問題C
競プロにちょっと興味を持った。
最速が出たので解説します。
dwacon2018-final-open.contest.atcoder.jp
(0ベースで)上からi段, 左からj番目のブロックの数字を とする。
+-----+ | a00 | +-----+-----+-----+ | a10 | a11 | a12 | +-----+-----+-----+-----+-----+ | a20 | a21 | a22 | a23 | a24 | +-----+-----+-----+-----+-----+-----+-----+ | a30 | a31 | a32 | a33 | a34 | a35 | a36 | +-----+-----+-----+-----+-----+-----+-----+
ここで、xor をで表すと、頂点の数字は、
のように展開していくことができる。 i回展開すると頂点の数字 は によって表される。
xor 演算は結合的かつ交換的なので、 i回展開した式に が現れる回数を で表すと、
となるが、 なので、 とすれば、
となる。ただし、 である。
よって、 とすれば、 となり、 は0 または1 なので、 m = 1,…,M について、 が1となる全ての のxor を取れば良い。
とすれば、 なので、以下では、 を求める。
の漸化式
は、 に現れるため、 となるため、
という漸化式が得られる。
この漸化式を使ったDPによって、 個のブロックを上から順に の値で埋めていくことができるが、 なので間に合わない1。
そこで、フラクタル的な性質を用いる。
フラクタルを用いた漸化式
を埋めていくと、 シェルピンスキーのギャスケット のようなフラクタル図形が現れる。
図の全体を半分のサイズに縮小すると、上半分の図形とほぼ重なる。
実際、
となり、 は と同じ漸化式を満たすため、 である。
また、 である。 これは、次のように示せる:
は、 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' が存在するため、 文字列の個数は偶数となり、 である。
まとめると、i が偶数のとき、次のような漸化式が得られる。
の漸化式
i が偶数のとき、
i が奇数のとき、
まとめると、任意のi,j について、
この漸化式を使うことで、 を再帰的に で計算できる。
よって、全体の計算量は 。
実装は以下。
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; }