素直にやろうとすると、各機会についてカードの数字が小さい方から $b_i$ 枚まで、$c_i$ より小さければ書き換える、ということを繰り返すのが思いつく。
だが、それでは書き換える回数が最大 $NM$ 回と多くなりすぎて間に合わない。
よく考えると、書き換える行為は、以下のようにも言い換えられる。
さらにこれは、$M$ 回の機会をまとめて一度に計算できる。
ただし実際に $c_i$ のカードを $b_i$ 枚作っていては、やはりこれも最大 $NM$ 枚のカードができてしまい間に合わないので、 「$c_i$ のカードが $b_i$ 枚」をひとかたまりの情報に圧縮して、ソートする。
Pythonのcollections.Counterは、リストを渡すと各要素がいくつあるかのdict(っぽいオブジェクト)に変換してくれるので、初期状態のリストを作成する際に使える。
a = [2, 3, 4, 2, 2, 4] b = Counter(a) # => {2: 3, 3: 1, 4: 2} c = list(b.items()) # => [(2,3), (3,1), (4,2)]
import sys from collections import Counter n, m = list(map(int, input().split())) aaa = list(map(int, input().split())) cards = list(Counter(aaa).items()) for line in sys.stdin: b, c = map(int, line.split()) cards.append((c, b)) ans = 0 cnt = 0 for c, b in sorted(cards, reverse=True): if cnt + b >= n: ans += c * (n - cnt) break ans += c * b cnt += b print(ans)
数えあげ問題。
適当に2つのコマに着目する。そのマンハッタン距離を $d$ とする。
●・・・ ・・●・ d=3 ・・・・
この2つのコマを含む配置というのは何通りあるかというと、 残り $NM-2$ 個のマスに $K-2$ 個のコマを置くパターン数なので、${}_{NM-2}C_{K-2}$ で計算できる。
つまり、それだけの個数の配置の1回1回のコスト計算時に、$d$ が1回ずつ足されていく。
この ${}_{NM-2}C_{K-2}$ はどの2コマでも変わらないのでまとめてしまえる。
$\sum_{i,j} d_{i,j} \times {}_{NM-2}C_{K-2}$
これを求めるとよい。が、実際に全ての2コマの組み合わせで計算していては間に合わない。
マンハッタン距離は、縦成分と横成分に分けて別々に計算してもよいので、分けて考える。 とりあえず横成分で考える。
ある1コマを $x$ に置いたとすると、もう1コマ置いた時のコストの合計は、以下のようになる。
1 x M ・・・ .... ・●・ .... ・・ x-1 x-3 .... 1 1 .... M-x x-2 M-x-1 1+2+...+(x-1) + 1+2+...+(M-x) => x(x-1)/2 + (M-x+1)(M-x)/2
これを各 $x$ で求めて合計すると、ある1行の横方向のコストの合計となる。
実際には縦方向もあるため、最初の1コマの行が $N$ 通り、もう1コマの行が $N$ 通りなので、$N^2$ をかけると全体の横方向のコストの合計となる。
縦方向のコストについても同様に求め、横方向と足し合わせると $\sum_{i,j} d_{i,j}$ が求められる。
n, m, k = list(map(int, input().split())) MOD = 10 ** 9 + 7 t = 0 pre = [0] for i in range(1, max(n, m) + 1): t += i pre.append(t) def calc_base(n, m, pre): base = 0 for i in range(n // 2): base = base + (pre[i] + pre[n - i - 1]) * 2 % MOD if n % 2 == 1: i = n // 2 base = (base + pre[i] * 2) % MOD return base * m * m % MOD bi = calc_base(n, m, pre) bj = calc_base(m, n, pre) def prepare(n, MOD): f = 1 for m in range(1, n + 1): f *= m f %= MOD fn = f inv = pow(f, MOD - 2, MOD) invs = [1] * (n + 1) invs[n] = inv for m in range(n, 1, -1): inv *= m inv %= MOD invs[m - 1] = inv return fn, invs nm = n * m - 2 f, inv = prepare(nm, MOD) print((bi + bj) * f * inv[k - 2] % MOD * inv[nm - k + 2] * inv[2] % MOD)
1 a b
: $g(x)=f(x)+|x−a|+b$ として $f(x)$ を $g(x)$ で置き換える2
: $f(x)$ の最小値を与える $x$ およびその最小値を出力する。そのような $x$ が複数存在する場合には最小の $x$ を答える$f(x)$ の更新がどのように行われるかというと、単純に加算で2つの項が加えられることになる。
$i$ 回目の更新クエリで与えられた数を $a_i,b_i$ とすると、$k$ 回目の更新後には以下のようになっている。
\begin{eqnarray} f(x) &=& |x-a_1|+b_1+|x-a_2|+b_2+...+|x-a_k|+b_k \\ &=& (|x-a_1|+|x-a_2|+...+|x-a_k|) + (b_1+b_2+...+b_k) \end{eqnarray}
ここで $b$ の部分は定数なので、最小値を考える上で重要なのは絶対値がついた部分となる。
このような差分の絶対値の和は、$x$ を $a=\{a_1,a_2,...,a_k\}$ の中央値とすることで最小値を取る。
a1 a2 ... a(m-1) am a(m+1) ... a_k 昇順にソートしたa、中央値はam ~~~~~~~~~~~~~~~~~~~ ~~~~~~~~~~~~~~~~ 左右は同数(t個)
$a$ の要素数が偶数の場合は中央の2数の間ならどこでも最小値を取るが、この問題ではそのような $x$ のうち最小を答えるので、中央の2数の小さい方の要素となる。
さて、中央値を使えば最小値を与える $x$ が求められることまでは分かった。残る問題は、
何通りかの方法があるが、ここでは優先キューを2つ使う方法を考える。以下のデータを用意する。
新しく $a$ に $a_i$ を加えるとき、lowとhighの要素数が等しいか、lowの方が1だけ大きくなるようにする。すると、中央値は常にlowで次にpopされる要素として求められる。
次に $|x-a_1|+|x-a_2|+...$ の値だが、これはlow, highそれぞれ以下のように求められる。
これに $b$ の値を足すと、$f(x)$ が求められる。
import sys from heapq import heappush, heappushpop Q = int(input()) high = [] low = [] sum_dh, sum_dl = 0, 0 sum_b = 0 buf = [] for qi, line in enumerate(sys.stdin): q = list(map(int, line.split())) if len(q) == 1: x = -low[0] ans_l = x * len(low) - sum_dl ans_h = sum_dh - x * len(high) buf.append('{} {}\n'.format(x, ans_l + ans_h + sum_b)) else: _, a, b = q sum_b += b if len(low) == len(high): h = heappushpop(high, a) heappush(low, -h) sum_dh += a - h sum_dl += h else: l = -heappushpop(low, -a) heappush(high, l) sum_dl += a - l sum_dh += l print(''.join(buf))