perogram

1163B2 - Cat Party (Hard Edition)

Quiz

https://codeforces.com/contest/1163/problem/B2

Submit

https://codeforces.com/contest/1163/submission/54007477

問題設定

  • 配列Aの前からx個を見て、その中の1つだけを除外して、他の値の頻度が同じなら、そのxはOK
    • [2,2,1,1,5,4,4]なら5を除外すれば、他の値の頻度は2で揃うのでx=7はOK
  • OKなるxの最大値を求めよ

解法

(こるとんさんの引用です)

補足

  • 公式解説
  • の通り、4パターンがOKとなる
    • 全部1
      • 1, 1, 1, 1
    • 1つだけ頻度1で、それを消せば他の頻度が同じ
      • 5, 5, 1, 5
      • 10, 10, 20, 30, 30 (20(頻度1)を消す)
    • 1つだけ削れば全部同じ数になる
      • 2, 2, 2, 3, 3, 3, 4, 4, 4, 4 (4だけ頻度が1多いので削ればOKとなる)
    • 全部が同じ値
      • 7, 7, 7, 7
  • これらの4パターンを判定するのに十分な統計値を持っておけばよい