AtCoder ABC143-Fを解いた
最近、AtCoderをやっているのですが解いた感想などを置く場所としてこのブログを再利用することにしました。どうせ複数のブログなどを持っても管理できないし。
ABC143-Fを解いていたのですが詰まってしまって苦労したのですが、解説とも違った解き方だったようなので軽くまとめます。
- 問題
高橋くんは 枚のカードを持っています。 番目のカードには整数 が書かれています。
高橋くんは整数 を選びます。そして、以下の操作を何度か繰り返します。
- 書かれている整数が互いに異なるちょうど 枚のカードを選び、食べる（食べたカードは消滅する）
のそれぞれに対して、操作を行える最大の回数を求めてください。
例として A=2, 1, 2の時、B1 = 3, B2 = 1, B3 = 0となります。(Bi : K=iの時の答え)
明らかにAは並び替えてもよくて、また各Aiの個数が大事であることがわかります。そこでAの個数分布を求めてSortしたもの, Siを準備します。Aが全て別の数字ならS=(1,1,...1)になるし、Aが全て同じ数字ならS=(N)です。この時、一度の操作はSのなかからk個選んでそれぞれの値を-1する操作と表せます。最大の操作をしたあとにSi>0となっているような要素は0~k-1個あることがわかります。このとき、どこが残るかというとSのうち大きいところ、ソート済みなので後ろの連続したいくつかが残りそうです。
この残る個数をlとします。l<Kです。残らない前半部(S_0, .. ,S_{m-l})とその次の値S_{m-l+1}が満たすべき条件はSum*1 // (K-l) < S_{m-l+1}です。(1式)
lを固定すると式を満たす最小のK=K1が見つかります。(★ 後述しますが記事を書いたきっかけです)
この最小のK1以上のKについて答えはSum*2 //(K-l)です。
lは大きい方から固定していき、一度答えが求まったKは更新しません。(あるlについて1式を満たす場合、それ以下のlも満たすがそのような操作は不可能)
はじめて説明を書こうとしましたが手元にあった証明もちゃんと書き直すと面倒なことがわかってしまい省略してしまいました。抜けがたくさんあると思います。今度復習したときに加筆します。
★ a//k<bとなる最小のkを求めるのって簡単でしょうか。少し悩んでしまいました。式変形するとa//k<b <=> (a-a%k)/k<b <=> a/k - c < b (0<=c<1) <=> a/(b+c)<k
結局kの候補はfloor(a/(b+1)) かfloor(a/(b+1)) +1のどちらかになるからはじめの式に入れて確認すればいい感じでしょうか。基本的な事柄っぽいですがすっきりせず。
