コンテスト中AC:A〜F

D - Flipping and Bonus

説明のため、お金をスコア、コイントスによって表か裏かを選んでスコアを得ることを操作と呼びます。

その時々の操作後のスコアを最大化するような貪欲法は使えません。
そこで、操作回数とカウンタの最大値が $N\leq 3000$ であり、小さいことから、DPできないか考えます。

$dp[i][j]:=$ $i$ 回目の操作終了後にカウンタが $j$ の時のスコアの最大値

このDPテーブルの大きさ(状態数)は $N^2 \leq 9\times 10^6$ となり十分小さいです。

次に $dp[i][j]$ への遷移を考えますが、その前にカウンタで得られるスコアについて、次のようにしておきます。

カウンタが $x$ の時のスコアを $D_x$ とする。なお、 $x$ が $C_1,\ \cdots C_M$ に含まれていない場合は、 $D_x=0$ とする。

$j\geq 1$
$i-1$ 回目終了後にカウンタが $j-1$ の状態であって、 $i$ 回目にカウンタを $+1$ する操作(コイントスが表)となった場合に遷移します。この時、スコアとして $X_i$ と $D_{j}$ が加算されます。
$dp[i][j] \leftarrow dp[i-1][j-1]+X_i + D_j$
$j=0$
カウンタが0の場合は、 $i$ 回目でカウンタを $0$ にする操作をした時です。 $i-1$ 回目のカウンタの状態に関わらず遷移するので、 $i-1$ 回目のスコアの最大値となります。
$dp[i][j] \leftarrow max(dp[i-1][0],\ dp[i-1][1],\ \cdots ,\ dp[i-1][N])$

$j=0$ の時に $N$ 回、 $1\leq j \leq N$ の時に各 $1$ 回ずつの計算が必要となるため、 $i=1,2,\cdots ,N$ と更新していった時、各 $i$ について、 $2N-1$ 回の計算が必要となります。従って、遷移にかかる計算量は $O(N^2)$ です。
( $1\leq j \leq N$ の計算の際にmax値を同時に計算していけば、定数倍軽くなると予想されます。)

よって、計算量も問題なく、DPで解けることがわかりました。
Submission #33455701 - AtCoder Beginner Contest 261

E - Many Operations

ビット演算の問題は、2進数の各桁毎に考えるのが典型です。

非負整数 $S$ の2進数表記の $d$ 桁目を $S^d$ と表すことにします。

非負整数 $X$ に対して操作 $1$ から操作 $3$ までを実行した場合を例に考えます。
操作1,2,3はそれぞれ $and,\ or,\ xor$ であったします。また、求めたい値を $Y_3$ とします。
つまり、

$Y_3 = ((X\ and\ A_1)\ or\ A_2)\ xor\ A_3$

です。
ここで、 $d$ 桁目のみに着目しても以下が成り立ちます。

$Y_3^d = ((X^d\ and\ A_1^d)\ or\ A_2^d)\ xor\ A_3^d$

2進数の桁は $0$ か $1$ しかありません。
そこで、

$B_3^d = ((0\ and\ A_1^d)\ or\ A_2^d)\ xor\ A_3^d$
$C_3^d = ((1\ and\ A_1^d)\ or\ A_2^d)\ xor\ A_3^d$

という風に予め計算しておくと、 $X^d$ が0か1かを判定することで、 $O(1)$ で $Y_3^d$ が求められます。
各桁について同様に求めることで、 $Y_3$ を構築できます。 $0\leq d \lt 30$ という制約があるため、高々30回の計算で済みます。

また、 $B_3^d,\ C_3^d$ は $B_2^d,\ C_2^d$ から以下の様に求められます。

$B_3^d = B_2^d\ xor\ A_3^d$
$C_3^d = C_2^d\ xor\ A_3^d$

これは操作3に限らず、一般の $i$ について、 $i-1$ の値から $i$ の値を求めることができます。

実装では、2進数表記で、00...0、11...1から始めて、順に $A_i$ とビット演算していきました。
このようにすれば、実装は少しシンプルになるのかなと思います。
詳細は実装を参照ください。
Submission #33463754 - AtCoder Beginner Contest 261

F - Sorting Color Balls

隣合う要素を入れ替えてソートするのはバブルソートです。バブルソートの最小交換回数は反転数に等しいです。そこで、反転数を軸にこの問題を考えます。

まず、色がない場合を考えます。
$i$ より前にあって、 $X_i$ より大きいものは自分より後ろに来なければいけないので、必ず $X_i$ と入れ替えなければいけません。
よって、その数を $c_i$ とすると、少なくとも $c_1+c_2+\cdots +c_N$ のコストがかかります。
これがコストの下界となります。コンテスト中は具体的な証明が思い浮かばなかったのですが、バブルソートの最小交換回数と反転数が等しいことから、実際にこれを達成できるはずと考えました。

次に、この考え方に従って、色がある場合を考えます。
$i$ より前にあって、 $X_i$ より大きいものでも、色が等しいものは交換にかかるコストが $0$ なので、無視できそうです。
そこで、 $i$ より前にあって、 $X_i$ より大きいものであり、かつ、色が異なるものの個数を $d_i$ とすると、少なくとも $d_1+d_2+\cdots +d_N$ のコストがかかると予想できます。

これが色を考慮した場合のコストの下界となります。具体的な証明はコンテスト中は浮かばなかったのですが、色が異なる場合と同様の操作をして、同色の分のコストを無視すれば良いだけなので、同様にこれが達成できるだろうと考えました。

結果として、この考え方は正しかったです。
おそらくこの証明は、Web解説やyoutube解説で示されているのかなと思います。

後は反転数の計算ですが、各色に対し、自分と異なる色のみの反転数を求めるのは難しいと考えました。
そこで、全体の反転数を求めた後、各色の反転数を引くことで求めました。
全体の反転数はFenwick Treeで求めました。
各色の反転数については、全色分のFenwick Treeの領域を確保するのが難しそうだったので、色ごとに $X_i$ を分類した後、分割統治法で求めました。

実装はコンテスト後に修正したものです。
Submission #33567025 - AtCoder Beginner Contest 261

geam1113’s diary

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

AtCoder Beginner Contest 261 参加記録

D - Flipping and Bonus

E - Many Operations

F - Sorting Color Balls