little star's memory

競プロの参加記など

yukicoder contest 276

のこさんの回。

コンテストページ

No.1298 OR XOR

xor系の問題はビットごとに見るのが定番。だから次の問題を考える。

  • $A \ \mathrm{or} \ B = B \ \mathrm{or} \ C = C \ \mathrm{or} \ A=0$
  • $A \ \mathrm{xor} \ B \ \mathrm{xor} \ C=0$

これは明らかに$A=B=C=0$のみ。

  • $A \ \mathrm{or} \ B = B \ \mathrm{or} \ C = C \ \mathrm{or} \ A=1$
  • $A \ \mathrm{xor} \ B \ \mathrm{xor} \ C=0$

これの解は$(A,B,C)=(1,1,0),(1,0,1),(0,1,1)$のいずれか。

Nの立っているビットが1個だけだと0になる数があるので不可能。そうでないときは、上の3パターンのうち2種類以上を使うと条件を満たす。ぼくはcyclicに使った。

Favした。

No.1299 Random Array Score

1回目に$A _ {j_1}$を選ぶと数列の各項は$A_i+A _ {j_1}$になり、2回目に$A _ {j_2}$を選ぶと各項は$A_i+2A _ {j_1}+A _ {j_2}$になる。これを続けて、K回目に$A _ {j_K}$を選ぶと、$A_i+2 ^ {K - 1}A _ {j_1}+2^{K-2}A _ {j_2}+\cdots+A _ {j_K}$となる。Sを元の数列の総和とするとき、K回操作を行った後の数列の総和は$S+N(2^{K - 1}A _ {j_1}+2^{K-2}A _ {j_2}+\cdots+A _ {j_K})$になる。この値を$1\le j_1,j_2,\ldots,j_K\le N$について総和をとると、$N ^ K S+N ^ K(2^{K - 1}S+2^{K-2}S+\cdots+S)=N ^ K \cdot S \cdot 2 ^ K$になる。期待値はこれを$N ^ K$で割って、$S\cdot 2 ^ K$となる。

No.1300 Sum of Inversions

こういうのは真ん中を固定するとよさそう。どこかの問題で見たテクニックな気がする。典型なのかな。

jを固定する。$i\lt j, A_i\gt A_j$をみたすiの個数を$cntL_j$、このiに関する$A_i$の総和を$sumL_j$とする。同様に$j\lt k, A_j\gt A_k$に関して$cntR_j, sumR_j$を定める。$A_i+A_j+A_k$を足していくことになるけど、$A_j$は$cntL_j\times cntR_j$個足される。$A_i$の分は$sumL_j\times cntR_j$、$A_k$の分は$cntL_j\times sumR_j$だけ足される。

あとは$cntL$や$sumL$を計算すればよい。これは転倒数を求めるときと同じように、BITを使うとできる。具体的にはAを座標圧縮したものをBとするとき

  • $cntL_j=j-bit.sum(0,b_i)$とする。
  • $bit[b_i]$を1増やす。

とすると$cntL$が求められる。1を増やすかわりに$A_i$を増やすと、$sumL$が求まる。

Favした。