パナソニックプログラミングコンテスト（AtCoder Beginner Contest 186）D,E,F問題メモ

パナソニックプログラミングコンテスト（AtCoder Beginner Contest 186）

中国剰余定理は何回見てもアルゴリズムが覚えられんのよね。

D - Sum of difference

• $N$ 個の整数 $A_1,...,A_N$ が与えられる
• $\displaystyle \sum_{i=1}^{N-1} \sum_{j=i+1}^{N}|A_j-A_i|$ を求めよ
• $2 \le N \le 2 \times 10^5$
• $|A_i| \le 10^8$

絶対値は「非負ならそのまま、負なら正負逆転」という操作と言い換えられ、「絶対に非負」という保証を作ってしまえば外せる。

そのためには、常に $A_j \ge A_i$ となればよくて、これは $A_i$ を昇順にソートすれば保証される。

ソートしても、「$A$ の全てのペアについて $|A_j-A_i|$ を求めて合計する」という処理内容は一緒で、 $|A_j-A_i|$ は、$i$ と $j$ を入れ替えても答えが変わらない。なのでソートしても問題ない。

これで $\displaystyle \sum_{i=1}^{N-1} \sum_{j=i+1}^{N}(A_j-A_i)$ を求めればよくなった。

このような「全ての2数ペアについて何らかの計算結果の総和を求める」系は、「1つの数が答えにどれだけ足されるか」というように個々の数に分解できないか考える。

すると、それぞれの数は「自分より大きい数とのペアでは $A_i$ 側になり負で作用する」「自分より小さい数とのペアでは $A_j$ 側になり正で作用する」ので、 自分より大きい数と小さい数の個数（＝ソート順で何番目か）がわかれば個々に分解できる。

自分と等しい数がある場合がちょっと気になるが、気にせずソート順を基準にして扱えばちゃんと打ち消されるので問題ない。

Python3

import sys

n, *aaa = map(int, sys.stdin.buffer.read().split())
aaa.sort()

ans = 0
for smaller_than_a, a in enumerate(aaa):
    larger_than_a = n - 1 - smaller_than_a
    ans += (smaller_than_a - larger_than_a) * a

print(ans)

E - Throne

• 円周上に $N$ 個の椅子が並べられていて、1つは玉座
• 高橋君は最初、玉座から時計回りに数えて $S$ 個隣の椅子に座っている
• 次の移動を繰り返して玉座に座りたい
  • いま座っている椅子から時計回りに数えて $K$ 個隣の椅子に移動する
• 高橋君が玉座に座ることができるか判定し、できる場合は最小の移動回数を求めよ
• $T$ 個のテストケースに答えよ
• $2 \le N \le 10^9$
• $1 \le S \lt N$
• $1 \le K \le 10^9$

N=12  S=3
   ○👑○
 ○      ○
○        Ｓ
 ○      ○
   ○○○

椅子の個数で移動を考える。

椅子の位置を考えると、$9,21,33,...,9+12k$ 個（$k \ge 0$）移動すると玉座に座れる。
移動を考えると、$K,2K,3K,...$ 個移動した位置に座れる。

この2つが一致する非負の最小の数を求めれば、それを $K$ で割った値が答え。求めるのには中国剰余定理が使える。

• $N$ で割ると $N-S$ 余り、$K$ で割ると $0$ 余る数を求めよ

Python3

from math import gcd


def chinese_remainder(rrr, mmm):
    n = len(rrr)
    r0 = 0
    m0 = 1
    for i in range(n):
        r1 = rrr[i] % mmm[i]
        m1 = mmm[i]
        if m0 < m1:
            r0, r1 = r1, r0
            m0, m1 = m1, m0
        if m0 % m1 == 0:
            if r0 % m1 != r1:
                return 0, 0
            continue
        g = gcd(m0, m1)
        if (r1 - r0) % g:
            return 0, 0
        u1 = m1 // g
        im = pow(m0 // g, -1, u1)
        x = (r1 - r0) // g * im % u1
        r0 += x * m0
        m0 *= u1
        if r0 < 0:
            r0 += m0
    return r0, m0


buf = []
t = int(input())
for _ in range(t):
    n, s, k = map(int, input().split())
    r, m = chinese_remainder([n - s, 0], [n, k])
    if m == 0:
        print(-1)
    else:
        print(r // k)

ちゃんとライブラリ整備しとこうね。

検索して出てくるコードは「2つのmodが互いに素を前提としているか」「答えが求まらないときにエラーにならないか」が一定じゃなくて、どれ使えばいいかわからん問題が発生する。

上記のコードは AtCoder Library を移植して、inv_gcd() に相当する機能はPython3.8より使える負の指数の pow() に置き換えたもの。

公式解説の方法。

$kK \equiv -S \mod{N}$ と立式して、$\mod{N}$ における $K$ のモジュラ逆数 $K^{-1}$ を求め、$k \equiv -SK^{-1} \mod{N}$ とすれば求められる。

これもPythonなら負の指数の pow() を使えばここまで簡単になるんだね。

Python3

from math import gcd

t = int(input())
for _ in range(t):
    n, s, k = map(int, input().split())
    g = gcd(n, k)
    if s % g != 0:
        print(-1)
        continue
    n //= g
    s //= g
    k //= g
    print(-s * pow(k, -1, n) % n)

F - Rook on Grid

• $H \times W$ の盤面の $i$ 行目 $j$ 列目を $(i,j)$ とする
• 盤上にははじめ、$(1,1)$ に将棋の飛車がいる
• 他に $M$ 個の障害物がそれぞれ $(X_i,Y_i)$ にある
• 飛車が2回の移動で到達できるマスの個数を求めよ
• $1 \le H,W \le 2 \times 10^5$
• $0 \le M \le 2 \times 10^5$

全てのマスについて考える $O(HW)$ は制約上無理。行ごと・列ごとに考えた結果を上手く集約する。

移動は↓→か→↓しかない。

□□□□□
□□■□□
□■□□□
□□□□□
□□■■□
□□□□□
■□■□□
□□□□■
□□□□□

まず、↓→を考える。
これは、各行で一番左に出てくる障害物まで取れる。1個も無い場合は全部取れる。その個数を整理する。

この内、1列目にある障害物はちょっと特殊で、障害物以降の行には行けない（回り込むには3手必要）ので、1回でも0が出てきて以降は全て0にする。

□□□□□  5
□□■□□  2
□■□□□  1
□□□□□  5
□□■■□  2
□□□□□  5
■□■□□  0
□□□□■  4 → 0
□□□□□  5 → 0

そんで、ここで求めた数字分は全部取れる。

↓→→→→  5
↓→■□□  2
↓■□□□  1
↓→→→→  5
↓→■■□  2
↓→→→→  5
■□■□□  0
□□□□■  0
□□□□□  0

あと取りたいのはここ（◇）。これは→↓で取る。今度は列についてさっきと同じことをしたいが、重複して数えないようにする必要がある。

  j  0 1 2 3 4  row
    ↓→→→→   5
    ↓→■◇◇   2
    ↓■  ◇◇   1
    ↓→→→→   5
    ↓→■■◇   2
    ↓→→→→   5
    ■  ■  ◇   0
            ■   0
                 0
col  6 2 1 4 7

ある列でたとえば $col[3]=4$ の時、「上から4行までの中で、$row$ の値が $3$ 未満」の行数が、新規に取れる◇となる。この場合は2個。

全体では $row$ の値が $3$ 未満の行はもっとあるのだが、$col[3]$ の処理時点では含まれないようにしたい。
そのためには、$col$ の値が小さい方から処理していくとよい。

幅 $W+1$ のFenwick木で、「今までで、$row$ の値が $x$ 未満の行が何個あったか」がすぐ取得できるように管理する。

Python3

from operator import itemgetter


class FenwickTree:
    def __init__(self, n):
        self.size = n
        self.tree = [0] * (n + 1)

    def sum(self, i):
        s = 0
        i += 1
        while i > 0:
            s += self.tree[i]
            i -= i & -i
        return s

    def add(self, i, x):
        i += 1
        while i <= self.size:
            self.tree[i] += x
            i += i & -i

    def debug_print(self):
        result = []
        for i in range(self.size):
            result.append(fwt.sum(i) - fwt.sum(i - 1))
        print(result)


h, w, m = map(int, input().split())
row = [w] * h
col = [h] * w
for _ in range(m):
    x, y = map(int, input().split())
    x -= 1
    y -= 1
    row[x] = min(row[x], y)
    col[y] = min(col[y], x)

for i in range(1, h):
    if row[i - 1] == 0:
        row[i] = 0

for j in range(1, w):
    if col[j - 1] == 0:
        col[j] = 0

col_s = sorted(enumerate(col), key=itemgetter(1))
fwt = FenwickTree(w + 1)

ans = 0
p = 0
for j, c in col_s:
    for i in range(p, c):
        fwt.add(row[i], 1)
        ans += row[i]
    p = c

    ans += fwt.sum(j)

print(ans)