geam1113’s diary

主にAtcoderのコンテストの備忘録を書きます。AtCoder緑と水色を行ったり来たりしています。

ARC129 参加記録

ARC 中央値下に凸なグラフ

コンテスト中AC:A,B

A - Smaller XOR
B - Range Point Distance

A - Smaller XOR

以下、整数は2進数で表現するものとします。

N = 10101としてシミュレートしてみます。

(1) xの4ビット以降に1がある場合

例えば、x = 100000とすると、

100000 XOR 010101 = 100000 > N

となります。このように、Nの1であるビットの内、最上位のものより上位にxが1を持つ場合、必ず、x XOR N > Nとなり、問題の条件を満たしません。

(2)xの5ビット目までが0で、4ビット目に1がある場合

xの4ビット目に1があると、10101の4ビット目の1が0になり、必ずx XOR N < Nを満たします(例x = 10000の時、10000 XOR 10101 = 00101)。

そのため、0〜3ビット目までは何でもよく、10000〜11111が条件を満たします。

(3)xの4ビット目までが0で、3ビット目に1がある場合

例えば、x = 01000とすると、

01000 XOR 10101 = 11101 > N

となり、必ず条件から外れます。

(4)xの3ビット目までが0で、2ビット目に1がある場合

(2)の場合と同様に100〜111までが必ず条件を満たします。

ここまでで分かることは、上位から考えてxに初めて1が登場する場所がi番目であり、更にNのi番目も1である場合、XORすると、i+1番目まではNに一致し、i番目が0になった整数となります。その整数は0〜i-1番目のビットによらず、Nより小さいことが確定します。(XORをするような桁DPでも同様の考え方が使われていると思います。)

反対に、Nのi番目が0であれば、Nより大きくなるのが確定します。

よって、Nの上位ビットから順に探索した時、i番目のビットが1なら、i番のビットが0である整数

x = 1000...0 〜 1111...1が条件x XOR N < Nを満たし、

$l \leftarrow max(L,1000...0)$

$r \leftarrow min(R,111...1)$

とした時、

$r - l + 1$

を答えに足せばよいです。

なお、[1000...0, 1111...1]がすべて、[L,R]の区間外の時、 $l \gt r$ となって個数が負になるので、

$max(r - l + 1,0)$

としておけばよいです(これがなくWA1)。

ちなみに、i番目が1である整数1000...0は、C++では

1LL<<i

と計算でき、1111...1は、

(1LL<<(i+1)) - 1

と計算できます。念の為、1LL<<(i+1)がlong long型を超えないことを確認しました。 $10^{18}\lt 2^{62}$ なので、問題ありませんでした。

提出コード

B - Range Point Distance

i番目までの(L,R)の組について考えます。

xを非常に小さくした時、

$max(L_1-x,L_2-x,...,L_i-x)$

を考えることになり、この時、Lのうち最大のものを $L_{max}$ として、

$L_{max}-x$

が最大となります。

同様にxが非常に大きい時、

$max(x-R_1,x-R_2,...,x-R_i)$

を考えることになり、この時、Rのうち最小のものを $R_{min}$ として、

$x-R_{min}$

が最大となります。

xを非常に小さいところから非常に大きいところまで動かすことを考えてみると、 $l-x$ が最大となるなら、それは $l=L_{max}$ の時だけで、同様に $x-r$ が最大となるならば、それは $r=R_{min}$ の時だけです。よって、この2つの距離のみを考慮すればよいことがわかります。

$R_{min} \geq L_{max}$ の時は、L,Rの組が1つしか存在しないか、またはL,Rを区間[L,R]とした時にすべての区間が共通する点を持つ場合なので、答えは0になります。

そうでない時、下のように数直線上に $R_{min},L_{max}$ があり、xを非常に小さいところ( $-\infty$ )から非常に大きいところ( $\infty$ )まで動かすことを考えてみます。

$(-\infty )$ ーーー $R_{min}$ ーーー $L_{max}$ ーーー $(\infty )$

区間 $[-\infty,R_{min}]$ では、 $L_{max}-x$ が常に最大となり、xを $-\infty$ から $R_{min}$ に1近づける度に $L_{max}-x$ は1小さくなります。

同様に、区間 $[L_{max},\infty]$ では、 $x-R_{min}$ が常に最大となり、xを $\infty$ から $L_{max}$ に1近づける度に $x-R_{min}$ は1小さくなります。

上記考察より、xは区間 $[R_{min},L_{max}]$ のどこかに置いた方が良いことがわかります。この区間内でxを $R_{min}$ から $L_{max}$ まで1ずつ動かすとことを考えます。

この区間の中央値を $M$ とします。

$R_{min}$ から $M$ までは、 $L_{max}-x$ が最大となって、xをMに1近づける度に $L_{max}-x$ は1小さくなります。

Mを境に、 $x-R_{min}$ が $L_{max}-x$ より大きくなります。xをMから $L_{max}$ に1近づくたびに $x-R_{min}$ は1大きくなります。

上記考察より、距離の最大値(すなわち、 $max(x-R_{min},L_{max}-x)$ )は、下に凸のグラフとなることがわかります。

したがって、xが中央値の時、すなわち $x = M = \frac{L_{max}+R_{min}}{2}$ の時に距離は最小となります。

（ $L_{max}+R_{min}$ が奇数の場合、切り上げると $x-R_{min}$ が、切り捨てると $L_{max}-x$ が最大となりますが、距離は同じです。）

距離などを考える問題は中央値が問題となるような時が多いような気がします。

提出コード