ABC216 参加記録 - geam1113’s diary

コンテスト中AC：A, B, C, D

C - Many Balls

操作を逆順に考えるのは典型です。Nから始めて0にすることを考えると、魔法Aは-1、魔法Bは÷2することになります。

すると、奇数なら魔法Aしかできず、偶数なら魔法Bを使用する方が0に近づけます。

奇数ならA、偶数ならBを繰り返し、最後に操作列を逆順にすれば解が得られます。

提出コード：https://atcoder.jp/contests/abc216/submissions/25423537

D - Pair of Balls

実装がややこしかった問題。実装ミスでWAを量産しています。

集合 $S_1,\ S_2$ を以下のように定義します。

$S_1$ : 筒の一番前に1つだけ存在する色の集合

$S_2$ : 筒の一番前に2つ存在する色の集合

色 $x$ が先頭である場合、 $S_1$ に色 $x$ が存在しなければ、 $S_1$ に挿入します。

そうでなければ、 $S_1$ から $x$ を削除し、 $S_2$ に $x$ を挿入します。これを挿入操作と呼ぶことにします。

初めに、全ての筒の先頭の色に挿入操作を行います。

そして、集合 $S_2$ が空でない限りはペアが存在することになるので、以下の操作を繰り返します。

1. $S_2$ から色 $x$ を1つ取り出す。

2. 色 $x$ を先頭にもつ2つの筒 $M_i,\ M_j$ から先頭の $x$ を取り除く

3. $M_i,\ M_j$ が空でなければ、現在先頭の色に挿入操作を行う

$S_2$ が空になった時、 $S_1$ に色が残っていなければ、答えはYesです。そうでなければ、Noです。

集合の管理はC++ならsetを使えば検索、挿入、削除をlog時間で行えます。

$M_i,\ M_j$ を特定する操作は、挿入操作の時に各色について筒のインデックスを記録しておけば $O(1)$ で得られます。

提出コード：https://atcoder.jp/contests/abc216/submissions/25437223

E - Amusement Park

コンテスト後に解説なしで解けました。コンテスト中は、K回以内で得られる満足度Xを二分探索する思考に陥っていました。

与えられた操作回数以内で最大化するような問題は二分探索を疑います。

今回の問題では、最適な取り方は大きいものから順番に取っていくことです。

例として、 $A=\{6,5,2,4,2\}$ に操作した場合を示します。

重要部分を抜き出すと以下のように遷移します。

$\{6,5,2,4,2\} \rightarrow \{5,5,2,4,2\} \rightarrow \{4,4,2,4,2\} \rightarrow \{3,3,2,3,2\} \rightarrow$

$\{2,2,2,2,2\} \rightarrow \{1,1,1,1,1\} \rightarrow \{0,0,0,0,0\}$

これは各要素を棒グラフとみなし、縦軸が $X$ となるところで切断したような状況と同じです。 $X=3$ なら、 $\{3,3,2,3,2\}$ です。

では、操作回数 $K$ 回以内だと、どこまで小さい値で切断可能でしょうか。

操作回数は $X$ が大きくなるにつれて減少する、単調非減少（多分）な列なので、上記の問いに対して解を二分探索できます。

$K$ 回以内の操作で切断できるかの判定は、 $A_i$ が $X$ 以上なら $A_i-X$ 回の操作が必要で、そうでなければ0回なので、各 $A_i$ についてこの総和をとることで $O(N)$ で判定可能です。

$X$ が定まれば、まず、各 $A_i$ について、 $A_i$ 〜 $X+1$ までの満足度を取得できます。

もし操作可能回数が $K'$ 回残っていた場合、 $X = 0$ の時以外は $X$ は $K'$ 個より多く残っていることが保証されるので、追加で $K'\times X$ の満足度を取得できます。（もし $X$ の個数が $K'$ 個以下なら $X-1$ で切断できます。)

なお、 $X = 0$ の時も実装上は同じにして問題ありません(入力例2のような場合)。

これが満足度の最大値となり、解を得られます。計算量は $O(Nlog(A_{max}))$ です。

提出コード：https://atcoder.jp/contests/abc216/submissions/25455746

F - Max Sum Counting

コンテスト後に解説なしで解けました。

全ての部分集合の和について、それぞれ何通りあるかを得るのは、部分和DPにより可能です。しかし、そこに最大値が何かを情報として持つことはできません。(部分和DPについての説明は省略します。ネット上に詳しいものがあると思います。)

ここで、 $A_i$ をとる選択をしたときに、 $A_i$ が最大値であるようにできれば、情報を持つ必要がなくなります。具体的には $A_1...A_{i-1}$ が $A_i$ 以下であれば、 $A_i$ が必ず最大値となります。

上の状況を実現するため、 $A$ の要素の値を基準として昇順ソートします。

全ての部分集合は要素の順番を入れ替えてもできるものは同じであるため、ソートすることに問題がなく、これも解法のヒントとなり得ると思います。

ソートされていると、 $A_i$ をとる選択をした時に、 $B$ の和が $j$ となるのは、 $dp[i-1][j-B_i]$ 通りとなります。

よって、部分和DPで $A_i$ をとる選択をした時に、 $j \leq A_i$ である場合の $dp[i-1][j-B_i]$ の総和をとっていけば答えが得られます。

補足ですが、 $A_i$ を最大値にするためには、 $i+1$ 以降は全て取らない選択をする1通りしかないため、最大値が $A_i$ であるときの部分集合が何通りあるかは、 $i$ までの選び方にのみ依存します。

提出コード：https://atcoder.jp/contests/abc216/submissions/25459401