大手前プロコン 2019 C - カード並べ 2 (Arranging Card 2)

https://atcoder.jp/contests/otemae2019/submissions/8913567

• 答えが単調減少する = 原因が何か考える
• ans = min(ans, nyaa) で処理できる

答えが単調減少していくことから原因が何か考えると、数列BにおけるA[i]の個数 > 数列BにおけるA[i+1]の個数 のとき減るような気がする。正確に言うと、floor(B全体のtally / 部分列]のtally) > floor(B全体のtally / 部分列]のtally) となるとき減少する。不等号が逆になるときは今までの答え最大値が引き継がれるので、以下の更新で処理できると分かる。

ans = min(ans, bmap[A[i]] / amap[A[i]] );

ただし、bmap[c]およびamap[c]は数列b全体と数列a部分列（範囲は]）におけるcの個数。数列Bは自由に順番を入れ替えて良いので、要素の順番は気にしなくて良いことに注意する。計算量はになる。