7K12 blog

猫でも分かるアルゴリズム解説

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

f:id:tkr987:20200603033733p:plain

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

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

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

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

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