コンテスト中AC:A〜F
D - Flipping and Bonus
説明のため、お金をスコア、コイントスによって表か裏かを選んでスコアを得ることを操作と呼びます。
その時々の操作後のスコアを最大化するような貪欲法は使えません。
そこで、操作回数とカウンタの最大値がであり、小さいことから、DPできないか考えます。
回目の操作終了後にカウンタが
の時のスコアの最大値
このDPテーブルの大きさ(状態数)はとなり十分小さいです。
次にへの遷移を考えますが、その前にカウンタで得られるスコアについて、次のようにしておきます。
カウンタが
の時のスコアを
とする。なお、
が
に含まれていない場合は、
とする。
回目終了後にカウンタが
の状態であって、
回目にカウンタを
する操作(コイントスが表)となった場合に遷移します。この時、スコアとして
と
が加算されます。
カウンタが0の場合は、回目でカウンタを
にする操作をした時です。
回目のカウンタの状態に関わらず遷移するので、
回目のスコアの最大値となります。
の時に
回、
の時に各
回ずつの計算が必要となるため、
と更新していった時、各
について、
回の計算が必要となります。従って、遷移にかかる計算量は
です。
(の計算の際にmax値を同時に計算していけば、定数倍軽くなると予想されます。)
よって、計算量も問題なく、DPで解けることがわかりました。
Submission #33455701 - AtCoder Beginner Contest 261
E - Many Operations
ビット演算の問題は、2進数の各桁毎に考えるのが典型です。
非負整数の2進数表記の
桁目を
と表すことにします。
非負整数に対して操作
から操作
までを実行した場合を例に考えます。
操作1,2,3はそれぞれであったします。また、求めたい値を
とします。
つまり、
です。
ここで、桁目のみに着目しても以下が成り立ちます。
2進数の桁はか
しかありません。
そこで、
という風に予め計算しておくと、が0か1かを判定することで、
で
が求められます。
各桁について同様に求めることで、を構築できます。
という制約があるため、高々30回の計算で済みます。
また、は
から以下の様に求められます。
これは操作3に限らず、一般のについて、
の値から
の値を求めることができます。
実装では、2進数表記で、00...0
、11...1
から始めて、順にとビット演算していきました。
このようにすれば、実装は少しシンプルになるのかなと思います。
詳細は実装を参照ください。
Submission #33463754 - AtCoder Beginner Contest 261
F - Sorting Color Balls
隣合う要素を入れ替えてソートするのはバブルソートです。バブルソートの最小交換回数は反転数に等しいです。そこで、反転数を軸にこの問題を考えます。
まず、色がない場合を考えます。
より前にあって、
より大きいものは自分より後ろに来なければいけないので、必ず
と入れ替えなければいけません。
よって、その数をとすると、少なくとも
のコストがかかります。
これがコストの下界となります。コンテスト中は具体的な証明が思い浮かばなかったのですが、バブルソートの最小交換回数と反転数が等しいことから、実際にこれを達成できるはずと考えました。
次に、この考え方に従って、色がある場合を考えます。
より前にあって、
より大きいものでも、色が等しいものは交換にかかるコストが
なので、無視できそうです。
そこで、より前にあって、
より大きいものであり、かつ、色が異なるものの個数を
とすると、少なくとも
のコストがかかると予想できます。
これが色を考慮した場合のコストの下界となります。具体的な証明はコンテスト中は浮かばなかったのですが、色が異なる場合と同様の操作をして、同色の分のコストを無視すれば良いだけなので、同様にこれが達成できるだろうと考えました。
結果として、この考え方は正しかったです。
おそらくこの証明は、Web解説やyoutube解説で示されているのかなと思います。
後は反転数の計算ですが、各色に対し、自分と異なる色のみの反転数を求めるのは難しいと考えました。
そこで、全体の反転数を求めた後、各色の反転数を引くことで求めました。
全体の反転数はFenwick Treeで求めました。
各色の反転数については、全色分のFenwick Treeの領域を確保するのが難しそうだったので、色ごとにを分類した後、分割統治法で求めました。
実装はコンテスト後に修正したものです。
Submission #33567025 - AtCoder Beginner Contest 261