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の最大値を求めよ
解法
Codeforces Round #558 (Div. 2) お疲れ様でした
— こるとん (@kyort0n) 2019年5月9日
A:算数 m=0がコーナーケース
B:むずくね？「最大値」と「各値を取る回数」と「出現回数が非零の値の数」を持てばうまくいく
C:むずくね？傾きとy切片(傾きinfinityならx切片)をsetで管理 答えに足し込むときは傾きのみ考慮
D:蟻本p.327
(こるとんさんの引用です)
補足
- 公式解説
- の通り、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
- 全部1
- これらの4パターンを判定するのに十分な統計値を持っておけばよい
