geam1113’s diary

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

ABC234 参加記録

ABC ウェーブレット行列 N進数変換

C - Happy New Year!
D - Prefix K-th Max
E - Arithmetic Number

C - Happy New Year!

非負整数 $x$ の2進数表記の1を2に変換する操作を考えます。操作後の値を $f(x)$ とします。すると、以下が言えます。

$x$ と $f(x)$ は一対一対応する。
非負整数の変換によって、0,2のみからなる整数の全てを得られる。
$x \lt y$ なら $f(x) \lt f(y)$ である。

以上から、 $K$ の2進数表記の1を2にすると答えを得られます。
提出コード

D - Prefix K-th Max

ウェーブレット行列が使えます。
ウェーブレット行列では、以下の関数が $O(logP_{max})$ で使えます。( $P_{max}$ は $P$ の要素の最大値で、今回は $N$ )

$quantile(s,e,r)$ :半開区間 $[s,e)$ の $r+1$ 番目に小さい値を返す。

$P$ を0-indexedとすれば、 $K \leq i \leq N$ について、 $quantile(0,i,K-i)$ で答えが計算できます。

計算量は、 $P$ のウェーブレット行列の構築がボトルネックとなり、 $O(NlogP_{max})$ です。
提出コード

E - Arithmetic Number

整数 $X$ の桁数を $d$ とします。
候補となる等差数 $Y$ の制約を考えてみます。

桁数 $i$ は $d\leq i \leq d+1$
公差 $j$ は $-9 \leq j \leq 9$
最上位桁 $k$ は、 $1 \leq k \leq 9$

更に、実際に $Y$ を構築する時に、 $i$ 回の計算が必要になります。
ワーストケースのおおよその計算量は、
$2 \times 19 \times 9 \times 18 = 6156$ となり、十分に小さいので、全探索可能です。

$Y$ の各桁の計算の過程で、桁の数 $t$ が $t \geq 10$ または $t \lt 0$ とならないものだけを答えの候補とします。その中で、 $Y \geq X$ を満たすもののうち、最小の $Y$ が答えです。

なお、条件1は $d+1$ 桁の整数について、必ずゾロ目が含まれ、これは公差0の等差数になることより導けます。
提出コード