AtCoder Beginner Contest 127 D,E,F問題メモ

AtCoder Beginner Contest 127

• AtCoder Beginner Contest 127 解説放送 - YouTube

D - Integer Cards

• カードが $N$ 枚あり、はじめは整数 $a_1,a_2,...,a_N$ が書かれている
• 書き換える機会が $M$ 回ある
• $i$ 回目の機会では、最大 $b_i$ 枚のカードを $c_i$ に書き換えることができる
• 最終的なカードに書かれた数字の和の最大値を求めよ
• $1 \le N \le 10^5$
• $1 \le M \le 10^5$

素直にやろうとすると、各機会についてカードの数字が小さい方から $b_i$ 枚まで、$c_i$ より小さければ書き換える、ということを繰り返すのが思いつく。

だが、それでは書き換える回数が最大 $NM$ 回と多くなりすぎて間に合わない。

よく考えると、書き換える行為は、以下のようにも言い換えられる。

• 既存の $N$ 枚に $b_i$ 枚の $c_i$ が書かれたカードを加え、数字の大きい方から $N$ 枚を残す

さらにこれは、$M$ 回の機会をまとめて一度に計算できる。

• 最初の $N$ 枚に、$b_1$ 枚の $c_1$ が書かれたカード、$b_2$ 枚の $c_2$ が書かれたカード、、、、を加え、大きい方から $N$ 枚を残す

ただし実際に $c_i$ のカードを $b_i$ 枚作っていては、やはりこれも最大 $NM$ 枚のカードができてしまい間に合わないので、 「$c_i$ のカードが $b_i$ 枚」をひとかたまりの情報に圧縮して、ソートする。

• 「$c_i$ のカードが $b_i$ 枚」を $(c, b)$ としてtupleで表現する
• カードの枚数を保持するリストを用意する。最初は空
• 初期状態のカードの数字を数え、$a$ が書かれたのが $b$ 枚なら $(a,b)$ をリストに追加する
• 各機会につき、$(c,b)$ をリストに追加する
• リストを大きい順にソートする
• 大きい方から $N$ 枚になるまで取り続ける

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)]

E - Cell Distance

• $N \times M$ マスの盤面
• コマを $K$ 個置く。$i$ 番目のコマは $(x_i,y_i)$ に置く。コマの場所は全て異なる。
• コマの配置によって、コストを以下のように定義する
  • 全ての2コマ間のマンハッタン距離の合計
  • つまり、$\sum_i \sum_j |x_i-x_j|+|y_i-y_j|$ ただし $i<j$
• 考えられる全てのコマの配置についてコストを計算し、その総和を $\mod{10^9+7}$ で求めよ
• $2 \le N \times M \le 2 \times 10^5$
• $2 \le K \le N \times M$

数えあげ問題。

適当に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}$ が求められる。

F - Absolute Minima

• 関数 $f(x)$ があり、はじめは定数関数 $f(x)=0$ である
• $Q$ 個のクエリが与えられるので、順番に処理せよ
• クエリは2種類ある
  • 更新 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個）

• $x$を $a_m$ から小さい方向に$d$ずらすと、$a_m$より小さい $t$ 個の要素との距離が $d$ ずつ縮まるが、$a_m$以上の $(t+1)$ 個の要素との距離が $d$ ずつ開く
• $x$を $a_m$ から大きい方向に$d$ずらすと、$a_m$より大きい $t$ 個の要素との距離が $d$ ずつ縮まるが、$a_m$以下の $(t+1)$ 個の要素との距離が $d$ ずつ開く
• ⇒ どちらにずらしても合計は増加してしまう
• ⇒ $x=a_m$ が最小値

$a$ の要素数が偶数の場合は中央の2数の間ならどこでも最小値を取るが、この問題ではそのような $x$ のうち最小を答えるので、中央の2数の小さい方の要素となる。

さて、中央値を使えば最小値を与える $x$ が求められることまでは分かった。残る問題は、

• $a$ に値が追加されていく中で、いつでも中央値を聞かれたらパッと答えられるようにしておく必要がある
• 中央値を代入したときの $|x-a_1|+|x-a_2|+...$ の値もパッと求められるようにしておく必要がある

何通りかの方法があるが、ここでは優先キューを2つ使う方法を考える。以下のデータを用意する。

• low: $a$ の内、中央値以下の要素を管理する優先キュー。最大値をpop
• high: $a$ の内、中央値より大きい要素を管理する優先キュー。最小値をpop
• sum_l: lowに入っている要素の合計
• sum_h: highに入っている要素の合計

新しく $a$ に $a_i$ を加えるとき、lowとhighの要素数が等しいか、lowの方が1だけ大きくなるようにする。すると、中央値は常にlowで次にpopされる要素として求められる。

次に $|x-a_1|+|x-a_2|+...$ の値だが、これはlow, highそれぞれ以下のように求められる。

• low: $(a_m - a_1) + (a_m - a_2) + ... + (a_m - a_m) = a_m \times |low| - sum_l$
• high: $(a_k - a_m) + (a_{k-1} - a_m) + ... + (a_{m+1} - a_m) = sum_h - a_m \times |high|$

これに $b$ の値を足すと、$f(x)$ が求められる。