yukicoder_956.txt

yukicoder No. 956 解説

＊問題文
No.956 Number of Unbalanced - yukicoder
https://yukicoder.me/problems/no/956


＊解法
数列 A に値 v が現れる個数を C(v) で表す。
各 v ごとに、v が過半数となる連続部分列の個数を数える。
その際、C(v) が大体 √(2N) より大きいか小さいかで場合分けをする。
大きい場合は、普通のセグ木を使って各 v ごとに O(N log(N)) 時間かけて普通に計算する。
小さい場合は、組合せの計算を頑張ると各 v ごとに O(C(v)^2) 時間で計算できる。つまり、連続部分列に含まれる v の右端と左端の位置を決めると、その場合の連続部分列の個数は O(1) で求められる。

Ｑ：なんで境界が √(2N) なんですか？
Ａ：√N でやってみたら TLE だったので……（適当）

Ｑ：組合せの計算って具体的に何？
Ａ：0 <= x < X かつ 0 <= y < Y かつ x+y < Z を満たす整数の組 (x, y) の個数を求める、みたいな問題が解ければよいです。これの解き方は……説明がめんどいので↓の提出コードを読んでね☆（手抜き解説）


＊提出コード
https://yukicoder.me/submissions/410221