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

AtCoder Beginner Contest 190

グラフ問題って実装でケアレスミスしてもどこがバグってるのかわかりづらい。
ライブラリもっときましょうね。

D - Staircase Sequences

問題

初項が整数、公差が1、項数が有限の等差数列で、和が $N$ となるものの個数を求めよ
$1 \le N \le 10^{12}$

解法

等差数列の和といえば、初項 $a$、公差 $d$、項数 $k+1$（$k \ge 0$）として、総和は $\dfrac{(k+1)(a+(a+dk))}{2}$ となる。

これが $N$ となればよいので、$d=1$ を代入して整理すると $2N=(k+1)(2a+k)$。

各変数は整数なので、$2N$ の約数を列挙して $(k+1, 2a+k)$ の組を全て調べればよい。これが $a$ を整数として成り立つなら、そのような等差数列を作れる。

約数列挙プログラム（感謝）
- 約数を高速で列挙するコード(Python) - Qiita

Python3

def make_divisors(n):
    lower_divisors, upper_divisors = [], []
    i = 1
    while i * i <= n:
        if n % i == 0:
            lower_divisors.append(i)
            if i != n // i:
                upper_divisors.append(n // i)
        i += 1
    return lower_divisors + upper_divisors[::-1]


n = int(input())
divisors = make_divisors(2 * n)
ans = 0
for d in divisors:
    k = 2 * n // d - 1
    if (d - k) % 2 == 0:
        ans += 1

print(ans)

よく見ると $(k+1,2a+k)$ は必ず偶数・奇数が異なり、またそれさえ満たせば必ず整数解を作れるので、そのことを利用する解法もある。

つまり、$N$ を2で割れるだけ割った結果を $M$ とすると $M$ の約数は必ず奇数、それとかけあわせて $2N$ となる相方は必ず偶数となる。
あとは約数1個につきどちらが $k+1$ でどちらが $2a+k$ かの2通りあるので、$Mの約数の個数 \times 2$ が答えとなる。

E - Magical Ornament

問題

$N$ 種類の石がそれぞれ無限個ある
一列に並べて飾りを作る
その際「種類 $a_i$ と $b_i$ の石は隣り合わせられる」というルールが $M$ 個あり、これ以外は隣りあわせてはいけない
$K$ 種類 $c_1,c_2,...,c_K$ の石をそれぞれ1個以上含む飾りを作れるか判定し、作れるなら石の最小個数を求めよ
$1 \le N,M \le 10^5$
$1 \le K \le 17$

解法

始点に戻らなくてよい巡回セールスマン問題。直帰型と呼ぼう。¹⁾

一列に並べるので、$c_i$ に含まれるある石からある石へ最短で繋げて、を繰り返すのがよい。
枝分かれしていいならハブのような石の存在を気にしなきゃいけないけど、その必要は無い。

なので、まずは「隣り合わせられる石のルール」1つをグラフの長さ1の辺1本とみなし、$c_i$ に含まれる全頂点間の最短距離を求める。
ここで、$N$ 頂点全ての点間の最短距離を求めるのはTLE,MLEなので注意。

そもそも到達できない2頂点があれば、不可能。

求められたら、$K$ 頂点で巡回セールスマン。

Pythonではライブラリが豊富なので、「巡回セールスマン」で検索してもAtCoderでは使えないライブラリとか近似解法の説明とかが出てくる。
「競プロ」とか添えて検索するとよい。

Python3

巡回セールスマンもDPの一種なので、実装に配る方針ともらう方針がある。もらう方がイテレート数が少なそうだけど、配る方がわかりやすいか。

from collections import deque


def bfs(s, links, targets):
    q = deque()
    q.append((0, s))
    stacked = {s}
    k = len(targets)
    dists = [INF] * k
    g = 0
    while q:
        c, v = q.popleft()
        if v in targets:
            dists[targets[v]] = c
            g += 1
        for u in links[v]:
            if u in stacked:
                continue
            q.append((c + 1, u))
            stacked.add(u)
    if g == k:
        return dists
    print(-1)
    exit()


n, m = map(int, input().split())
links = [set() for _ in range(n)]
for _ in range(m):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    links[a].add(b)
    links[b].add(a)

k = int(input())
ccc = [c - 1 for c in map(int, input().split())]

INF = 10 ** 18
targets = {c: i for i, c in enumerate(ccc)}
dists = [bfs(c, links, targets) for c in ccc]

dp = [[INF] * (1 << k) for _ in range(k)]
for i in range(k):
    dp[i][0] = 0
    dp[i][1 << i] = 0

for b in range(1, (1 << k) - 1):
    nl = set()
    i = 0
    t = b
    while t:
        if t & 1:
            nl.add(i)
        t >>= 1
        i += 1

    for v in range(k):
        if v in nl:
            continue
        tmp = INF
        for u in nl:
            tmp = min(tmp, dp[u][b] + dists[u][v])
        dp[v][b | (1 << v)] = min(dp[v][b | (1 << v)], tmp)

print(min(dp[i][-1] for i in range(k)) + 1)

F - Shift and Inversions

問題

$0,1,...,N-1$ の順列 $a_0,a_1,...,p_{a-1}$ が与えられる
この順列を、$k=0,1,...,N-1$ 回シフトさせた数列の転倒数を、各 $k$ について求めよ
$1 \le N \le 3 \times 10^5$

解法

転倒数の意味の1つが「正しくない順序（$i \lt j$ なのに $a_i \gt a_j$）となっているペア数」とわかっていれば、差分に着目すれば比較的簡単。
E問題よりすぐ解けた人も多そう。

まずは、$k=0$ の時の転倒数を求める。

転倒数

さて、1個シフトしたらどうなるか。

3 1 4 0 2
    ↓
  1 4 0 2 3

この時、動かす数（3）以外のペアは変わらない。

そして、

$(3,4)$ のように従来正しい順序だったペアは必ず転倒する
$(3,1)$ のように従来転倒していたペアは必ず正しい順序になる

これで差分が計算できる。

今回は親切なことに順列なので、

従来正しいペアの個数＝動かす数 $a_i$ より大きい数の個数＝ $N-a_i-1$ 個
従来転倒していたペアの個数＝ $a_i$ より小さい数の個数＝ $a_i$ 個

と、$a_i$ の値だけからその個数が計算できる。

Python3

import sys
from operator import add


class FenwickTreeInjectable:
    def __init__(self, n, identity_factory, func):
        self.size = n
        self.tree = [identity_factory() for _ in range(n + 1)]
        self.func = func
        self.idf = identity_factory
        self.depth = n.bit_length()

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

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

    def lower_bound(self, x, lt):
        """
        累積和がx以上になる最小のindexと、その直前までの累積和

        :param lt: lt(a, b) で a < b ならTrueを返す関数
        """
        total = self.idf()
        pos = 0
        tree = self.tree
        func = self.func
        for i in range(self.depth, -1, -1):
            k = pos + (1 << i)
            new_total = func(total, tree[k])
            if k <= self.size and lt(new_total, x):
                total = new_total
                pos += 1 << i
        return pos + 1, total


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

fwt = FenwickTreeInjectable(n, int, add)
ans = 0

for i, p in enumerate(aaa):
    ans += i - fwt.sum(p)
    fwt.add(p + 1, 1)

buf = [ans]
for a in aaa[:-1]:
    ans += n - 2 * a - 1
    buf.append(ans)

print('\n'.join(map(str, buf)))

¹⁾

最短ハミルトンパスという名前がちゃんとある

目次

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

D - Staircase Sequences

問題

解法

E - Magical Ornament

問題

解法

F - Shift and Inversions

問題

解法