AtCoder Beginner Contest 190 D,E,F問題メモ
D - Staircase Sequences
問題
解法
等差数列の和といえば、初項 $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$ を整数として成り立つなら、そのような等差数列を作れる。
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$
解法
始点に戻らなくてよい巡回セールスマン問題。直帰型と呼ぼう。1)
一列に並べるので、$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$ の値だけからその個数が計算できる。
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)))
