素直にやろうとすると、各機会についてカードの数字が小さい方から $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))