AtCoder Beginner Contest 474 E,F,G問題メモ

AtCoder Beginner Contest 474

昼開催なの見落としてた。。。

E - One Time Coupon

• ある店では $N$ 種類の商品が売られています。各商品は何回でも購入することができます。
• $i$ 種類目 $(1\le i\le N)$ の商品は以下の $2$ 通りの方法で買うことができます：
  • クーポンを使わずに $A_i$ 円で購入し、クーポンを $1$ 枚もらう。
  • クーポンを $1$ 枚使い、$B_i$ 円で購入する。
• 最初、あなたはクーポンを $1$ 枚も持っていません。
• 全ての商品を $1$ 回以上購入するために必要な金額の最小値を求めてください。

• $T$ 個のテストケースが与えられるので、それぞれについて答えを求めてください。

• $1\le T\le 2\times 10^5$
• $1\le N\le 2\times 10^5$
• $1\le B_i \lt A_i \le 10^9$
• 全てのテストケースにおける $N$ の総和は $2\times 10^5$ 以下
• 入力される値は全て整数

クーポンを貰うために同じ商品を $2$ 回以上買ってもよい、という点が少し難しさを上げている。

商品を（多重）集合 $S,T$ に分ける。$S$ は定価で買う商品、$T$ はクーポンを使って買う商品を表す。

• $|S| \ge |T|$
• 全ての商品が、$S$ か $T$ のいずれかに1個以上存在
• $S$ には同じ商品が複数あっていい

$S,T$ の両方に存在する商品はないとしてよい。あるなら $T$ 側は明らかに省ける。

また、どの $S$ 側の商品 $i$ と $T$ 側の商品 $j$ をとっても、$A_i-B_i \le A_j-B_j$ である。
もしそうでないなら、$j$ を $S$、$i$ を $T$ に入れ替えることでコストを減らすことができる。

よって、商品を $A_i-B_i$ をキーとしてソートし、indexも改めてその順に振り直すとする。

境界線を全探索する。つまり、$s=1,2,...$ に対し、 $S$ 側にindex $s$ 以下の商品、$T$ 側にindex $s+1$ 以上の商品を入れた場合のコストを考える。

$i=s+1,...,N$ はコスト $B_i$ で買うことになる。

$i=1,...,s$ はコスト $A_i$ で買うことになる。
さらに $|S| \ge |T|$ とするためには、$\max(0,N-2s)$ 枚の追加のクーポンが必要となる。 これは明らかに $s$ 側の中で $A_i$ が最小の商品を繰り返し購入した方がよい。

つまり、コストは以下のようになる。ソート後の $A_i,B_i$ の累積和と累積minを計算しておけば、$O(1)$ で求められる。

• $\displaystyle \sum_{i=1}^{s}A_i + \sum_{i=s+1}^{N}B_i + \min_{1 \le i \le s}(A_i) \times \max(0,N-2s)$

これを考えると、$A_i-B_i$ でのソート時、「同率であれば $A_i$ が小さいものを先に持ってきた方がよい」。 つまり、ソートのキーは $(A_i-B_i,A_i)$ とする必要がある。

ソートのキーをそのように変更した上で、$s=1,2,...$ を全探索し、コスト最小値を求めればよい。

Python3

from heapq import heapify, heappop, heappush


def solve(n, items):
    diffs = []
    for i, (a, b) in enumerate(items):
        diffs.append((a - b, a, i))
    diffs.sort()

    acc_min_a = [1 << 60]
    acc_a = [0]
    acc_b = [0]
    for _, _, i in diffs:
        a, b = items[i]
        acc_min_a.append(min(acc_min_a[-1], a))
        acc_a.append(acc_a[-1] + a)
        acc_b.append(acc_b[-1] + b)

    ans = 1 << 60
    for i in range(1, n + 1):
        need_coupon = n - i
        extra_coupon = max(0, need_coupon - i)
        tmp = acc_a[i] + acc_min_a[i] * extra_coupon
        tmp += acc_b[n] - acc_b[i]
        ans = min(ans, tmp)
    return ans


t = int(input())
for _ in range(t):
    n = int(input())
    items = [list(map(int, input().split())) for _ in range(n)]
    ans = solve(n, items)
    print(ans)

F - Increment All Divisors

• 長さ $N$ の整数列 $A=(A_1,A_2,\dots,A_N)$ が与えられます。$A$ に対して、以下の操作を好きな回数行うことができます。
  • $1$ 以上 $N$ 以下の整数 $i$ を一つ選び、$i$ の正の約数であるようなすべての整数 $j$ について $A_j$ に $1$ を足す。

• $A$ の要素をすべて等しくすることが可能かを判定し、可能ならばそのために必要な操作回数の最小値を求めてください。

• $1 \leq N \leq 2 \times 10^5$
• $1 \leq A_i \leq 10^9$
• 入力される値はすべて整数

約数メビウス変換の応用。

• 高速ゼータ変換の約数版 O(N log(log(N))) - noshi91のメモ

• 約数ゼータ変換
  • ある数列 $A=(A_1,...,A_N)$ に対し、以下の $B$ を求める。
  • $B_i$ は「$i$ の倍数であるような全ての $A_i$ の総和」、$\displaystyle B_i = \sum_{i|j}A_j$
• 約数メビウス変換
  • 約数ゼータ変換された $B$ を $A$ に戻す。

本問題では、「揃える値 $m$」が決まっていれば、$B=(m-A_1,m-A_2,...,m-A_N)$ は「各 $i$ に何回加算されたか」を示す。 これを約数メビウス変換した結果 $C=(C_1,...,C_N)$ は、「各 $i$ を何回、操作の起点としたか」を表すことになる。 （ただし、$B$ が何らかの操作の結果として実際に実現可能なものである前提で）

i  1  2  3  4  5
A  1  3  4  5  6
                    m=6に揃えるなら
B  5  3  2  1  0
                    これを約数メビウス変換すると
C  0  2  2  1  0
                    よって、2に2回、3に2回、4に1回 操作すると A は 6 に揃うことが分かる

なお、いずれの操作においても $A_1$ には必ず $1$ 加算されるので、 もし $m$ に揃えるのが実現可能なら操作回数は $m-A_1$ である。 つまり、操作回数最小化の上で、$m$ は「実現可能な中での最小値」としてよい。

何をもって「実現可能」とするか？
これは「メビウス変換の結果、$C$ に負値が現れない」ことである。

では、実現可能な $m$ の範囲はどうやって探せばよいか？
ここで、$m$ を変数として「$m-A_i$」という一次式のままメビウス変換をおこなう。

i    1    2    3    4    5
A    1    3    4    5    6
B   m-1  m-3  m-4  m-5  m-6
C -2m+12  +2  m-4  m-5  m-6

すると、$C$ の各要素が非負となるために $m$ に求められる上限と下限が決定できる。 上記の場合、$i=1$ の時に $m \le 6$、$i=5$ の時に $m \ge 6$ が求められ、下限=上限=6 だとわかる。

この範囲が潰れてしまったら不可能。また、-2m-10 など、$m$ が正の範囲で正にできない値がある場合も不可能。

潰れなかったら下限の $m$ が最適値となり、$m-A_1$ が操作回数となる。

Python3

def get_spf(n):
    """ nまでの各数を割り切る一番小さな素数 """
    spf = list(range(n + 1))
    for i in range(2, n + 1, 2):
        spf[i] = 2
    for p in range(3, int(n ** 0.5) + 1, 2):
        if spf[p] == p:
            for m in range(p * p, n + 1, 2 * p):
                if spf[m] == m:
                    spf[m] = p
    return spf


def prime_factorize(x, spf):
    """ xを素因数分解、(素数, 個数)の配列で返す """
    factors = []
    prev = -1
    cnt = 0
    while x > 1:
        if spf[x] == prev:
            cnt += 1
        else:
            if prev != -1:
                factors.append((prev, cnt))
            prev = spf[x]
            cnt = 1
        x //= spf[x]
    if prev != -1:
        factors.append((prev, cnt))
    return factors


def get_divisor(x, spf):
    pf = prime_factorize(x, spf)
    res = [1]
    for p, c in pf:
        y = 1
        l = len(res)
        for _ in range(c):
            y *= p
            for i in range(l):
                res.append(res[i] * y)
    return res


def solve(n, aaa):
    if n == 1:
        return 0
    if n == 2:
        if aaa[0] <= aaa[1]:
            return aaa[1] - aaa[0]
        else:
            return -1

    spf = get_spf(n)
    divisors = [[]] + [get_divisor(i, spf) for i in range(1, n + 1)]

    aaa.insert(0, 0)
    bbb = [(1, -a) for a in aaa]
    for i in range(n, 1, -1):
        x, y = bbb[i]
        for d in divisors[i]:
            if i != d:
                bbb[d] = (bbb[d][0] - x, bbb[d][1] - y)

    k = 0
    for x, y in bbb[1:]:
        if x <= 0 and y <= 0:
            if x == 0 and y == 0:
                continue
            return -1
        if x >= 0 and y >= 0:
            continue
        if x < 0:
            continue
        y = abs(y)
        z = (y - 1) // x + 1
        k = max(k, z)

    ans = 0
    for x, y in bbb[1:]:
        z = x * k + y
        if z < 0:
            return -1
        ans += z
    return ans


n = int(input())
aaa = list(map(int, input().split()))
ans = solve(n, aaa)
print(ans)

G - LRUD Moving 2

• 正整数 $N,K$ が与えられます。
• $N\times N$ のマス目があり、上から $r$ 行目、左から $c$ 列目のマスをマス $(r,c)$ と表します。
• はじめ、コマがマス $(1,1)$ に置かれています。
• あなたは以下の操作をちょうど $N^2-1$ 回行い、最終的にコマをマス $(N,N)$ に移動させます：
  • 現在いるマスから、上下左右に隣接するマスへコマを $1$ マス移動させる。
• ただし、移動中に $N^2$ 個のすべてのマスをそれぞれちょうど $1$ 回ずつ訪れなければなりません。ここで、最初にコマが置かれているマス $(1,1)$ も訪れたマスに含めます。
• 右へ $1$ マス移動する操作の回数がちょうど $K$ 回となるような操作列が存在するか判定し、存在する場合はそのような操作列を $1$ つ求めてください。

• $T$ 個のテストケースが与えられるので、それぞれについて答えを求めてください。

• $1\le T\le 5\times 10^3$
• $2\le N\le 10^3$
• $0\le K\le N^2-1$
• 全てのテストケースにおける $N^2$ の総和は $10^6$ 以下
• 入力される値は全て整数

証明は難しいが、実験から何となく条件を推測するのは可能、という感じの問題。 こういうのコンテスト中にどこに置くかが難しそう。

可能な条件は、以下の通りである。

• ① $N$ は奇数
• ② $K$ は偶数
• ③ $N-1 \le K \le \dfrac{(N-1)(N+1)}{2}$ を満たす

①の証明: グリッドを市松模様で塗ると黒と白を交互に踏むことになる。 $(1,1)$ と $(N,N)$ は同じ色（仮に黒）になるが、 $N$ 偶数なら黒と白が同数になので、全体を踏みつつ黒で始まって黒で終われない。 $N$ は奇数である必要がある。

②の証明はかなり難しい。Editorialに2通りの説明がある。

③は、制約から算出可能な最小と最大の範囲内にあるかどうかとなる。以下で実際の構築方法とともに証明できる。

移動回数をそれぞれ $L,R,U,D$ とする。また、正方形以外のグリッドも考慮し、$H \times W$ とする。 トータルでの右・下移動回数を考慮すると、$R-L=W-1,D-U=H-1$ が成り立つ。 各値は非負で、$L+R+U+D=HW-1$ という式をまとめると、

• $R$ を最小にするなら、$L=0,R=W-1,U=\frac{(H-1)(W-1)}{2},D=\frac{(H-1)(W+1)}{2}$
• $R$ を最大にするなら、$U=0,D=H-1,L=\frac{(H-1)(W-1)}{2},R=\frac{(H+1)(W-1)}{2}$

が成り立つ。そしてこれらは実際に、牛耕式に辿ることで実現できる。

最大            最小
→→→→↓      ↓→↓→↓
↓←←←←      ↓↑↓↑↓
→→→→↓      ↓↑↓↑↓
↓←←←←      ↓↑↓↑↓
→→→→■      →↑→↑■
(H+1)(W-1)/2回  W-1回

上2行を使って横方向に行って帰ってくると、$K$ を $W-1$ 消費して $(H-2) \times W$ に帰着できる。
これが可能なら、貪欲に取ってよい。

不可能なら、左2列を使うことで $K$ を $2$ 消費して $H \times (W-2)$ に帰着できる。

帰着した新たな $(H',W',K')$ は必ず $W'-1 \le K' \le \dfrac{(H'+1)(W'-1)}{2}$ が成り立つので、最終的に $W'=1$ となり、$K'=0$ とすることが可能である。

Python3

def solve(n, k):
    if n % 2 == 0 or k % 2 == 1:
        return None

    def is_ok(h, w, k):
        lo = w - 1
        hi = (w - 1) * (h + 1) // 2
        return lo <= k <= hi

    if not is_ok(n, n, k):
        return None

    ans = []
    h = w = n
    while h > 1 and w > 1:
        if is_ok(h - 2, w, k - (w - 1)):
            ans.append('R' * (w - 1))
            ans.append('D')
            ans.append('L' * (w - 1))
            ans.append('D')
            h -= 2
            k -= w - 1
            continue

        if is_ok(h, w - 2, k - 2):
            ans.append('D' * (h - 1))
            ans.append('R')
            ans.append('U' * (h - 1))
            ans.append('R')
            w -= 2
            k -= 2
            continue

        raise NotImplementedError('ここにはこないよ')

    if h > 1:
        assert w == 1
        assert k == 0
        ans.append('D' * (h - 1))
    elif w > 1:
        assert k == w - 1
        ans.append('R' * (w - 1))

    ans = ''.join(ans)
    return ans


t = int(input())
for _ in range(t):
    n, k = list(map(int, input().split()))
    ans = solve(n, k)
    if ans is None:
        print('No')
    else:
        print('Yes')
        print(ans)