AtCoder Beginner Contest 465 D,E,F,G問題メモ
D - X to Y
問題文
整数 $X,Y$ と $2$ 以上の整数 $K$ が与えられます。
変数 $x$ があり、はじめ $x=X$ です。あなたは $x$ に対して以下の操作を $0$ 回以上何回でも行うことができます：
$\displaystyle \left\lfloor \frac xK \right\rfloor=y$ または $\displaystyle \left\lfloor \frac yK \right\rfloor=x$ を満たす整数 $y$ を選び、$x$ の値を $y$ に置き換える。
ここで、実数 $z$ に対し $\displaystyle \left\lfloor z \right\rfloor$ は $z$ 以下の最大の整数として定義されます。
$x=Y$ とするために必要な操作回数の最小値を求めてください。
制約
$1\le T\le 2\times 10^5$
$0\le X,Y\le 10^{18}$
$2\le K\le 10^{18}$
入力される値は全て整数
解法
$K$ 進数の数として考えると見通しが良くなる。
よって、$K$ 進数で表した時の互いの prefix が共通する部分は残してよくて、それ以外は削ったり付け足したりする必要がある。
とはいえ、実装の際には prefix とか考えずとも、「$X=Y$ となるまで $X$ と $Y$ の大きい方を $K$ で割る」操作回数を求めることで正答できる。
Python3
def solve(x, y, k):
ans = 0
while x != y:
if x > y:
x //= k
else:
y //= k
ans += 1
return ans
t = int(input())
for _ in range(t):
x, y, k = list(map(int, input().split()))
ans = solve(x, y, k)
print(ans)
E - Digit Circus
問題文
制約
$N$ は整数
$1 \leq N \lt 10^{500}$
解法
桁DP。1つ1つの条件は桁DPの問題として度々見るが、複数を一気に考えなければならないので落ち着いて処理する。
なお、「3つの条件のうち1つだけ満たす」などの文言から包除原理っぽくも見えるが、
この問題では「3の倍数であって3が使われてなくて2種類の数字しか使っていない」など、
条件の積を全て管理しても状態数がそこまで大きくならないので、DPは1回でいい。
以下の情報を整理しとけばいい。
$\mathrm{DP}[i,j,k]:=$
上から $i$ 桁目まで見て、$N$ 以下であることが確定していて、
これまでに使った数字の集合bitsetが $j$ で、
ここまでのmod3が $k$ であるような数字の個数
bitsetは、「十進表記に3が含まれるか」「十進表記は丁度3種類の数字が使われるか」の2つの判定に答えられる。
状態数は $2^{10}=1024$
mod3 は、そのまま $3$ の倍数かの判定に用い、状態数は $3$
遷移では、各状態から末尾に新規に何を置くかで $10$ 通り。
桁は $500$ 桁なので、全体で $1024 \times 3 \times 10 \times 500 = 1.536 \times 10^7$ 程度で、間に合う。
Python3
bitsetを、pop count が $4$ 以上になった時点でバーストと見なして全て同じ値（-1）とし、
代わりに'3'が含まれるかを別途boolで保持する実装により、状態数を少し節約しているが、
パフォーマンス的に向上してるかは微妙。
from collections import defaultdict
def solve(n):
MOD = 998244353
dp = {}
n_bitset = 0
n_inc3 = 0
n_mod3 = 0
is_first = True
for c in n:
ndp = defaultdict(int)
c = int(c)
# こっから始まる
if is_first == False:
for i in range(1, 10):
ndp[1 << i, int(i == 3), i % 3] += 1
# こっから N 以下が確定する。
for i in range(int(is_first), c):
bitset = n_bitset | (1 << i)
inc3 = n_inc3 | int(i == 3)
mod3 = (n_mod3 * 10 + i) % 3
if bitset.bit_count() > 3:
bitset = -1
ndp[bitset, inc3, mod3] += 1
ndp[bitset, inc3, mod3] %= MOD
is_first = False
# 既に N 以下が確定しているもの
for (bitset, inc3, mod3), pat in dp.items():
if bitset == -1:
for i in range(10):
new_mod3 = (mod3 * 10 + i) % 3
new_inc3 = inc3 | int(i == 3)
ndp[-1, new_inc3, new_mod3] += pat
ndp[-1, new_inc3, new_mod3] %= MOD
continue
bc = bitset.bit_count()
for i in range(10):
new_mod3 = (mod3 * 10 + i) % 3
new_inc3 = inc3 | int(i == 3)
if bitset & (1 << i) == 0:
if bc == 3:
ndp[-1, new_inc3, new_mod3] += pat
ndp[-1, new_inc3, new_mod3] %= MOD
else:
ndp[bitset | (1 << i), new_inc3, new_mod3] += pat
ndp[bitset | (1 << i), new_inc3, new_mod3] %= MOD
else:
ndp[bitset, new_inc3, new_mod3] += pat
ndp[bitset, new_inc3, new_mod3] %= MOD
dp = ndp
n_bitset = n_bitset | (1 << c)
n_inc3 = n_inc3 | int(c == 3)
n_mod3 = (n_mod3 * 10 + c) % 3
# print(f'{c=} {dp=}')
ans = 0
for (bitset, inc3, mod3), pat in dp.items():
bc = bitset.bit_count()
if int(bc == 3) + inc3 + int(mod3 == 0) == 1:
ans += pat
ans %= MOD
if int(len(set(n)) == 3) + int('3' in n) + int(n_mod3 == 0) == 1:
ans += 1
ans %= MOD
return ans
n = input()
ans = solve(n)
print(ans)
F - Sjeltzer?
問題文
ある冷蔵庫では、ドリンクに $6$ 桁の数字列を ID として割り振っています。
この冷蔵庫には $N$ 個のドリンクが保管されています。
$Q$ 個のクエリに答えてください。各クエリは $6$ 桁の数字列 $x, y$ の形式で与えられ、内容は以下の通りです。
制約
$N$ は整数
$1 \leq N \leq 3 \times 10^5$
$S_i$ は数字 (0-9) からなる文字列
$|S_i| = 6$
$S_1, \dots, S_N$ は相異なる
$V_i$ は整数
$1 \leq V_i \leq 10^9$
$Q$ は整数
$1 \leq Q \leq 3 \times 10^5$
各クエリにおいて、$x, y$ は数字 (0-9) からなる文字列
各クエリにおいて、$|x| = |y| = 6$
解法
仮にIDの桁が1桁なら、「IDが $x$ 以上 $y$ 以下のドリンクのサイズの総和は？」となって、単純な累積和問題であることはすぐ分かる。
これを6次元でやれ、という問題。
例えば2次元累積和なら以下の4つの点の足し引きで求められる。これは包除原理を使っている。
→2次元目
↓ (X1-1,X2-1). … (X1-1,Y2).
１ ┼───────┼ Acc[Y1,Y2] - Acc[Y1,X2-1] - Acc[X1-1,Y2] + Acc[X1-1,X2-1]
次 │ │
元 │ │
目 ( Y1 ,X2-1).│ (Y1,Y2).│
┼───────┼
6次元でも同様に、$2^6$ 個の累積和の位置を参照し、「$x_k-1$ と $y_k$ のうち、$y_k$ の方を採用した個数」が
偶数なら答えに正で寄与し、奇数なら負で寄与する、として合計すれば答えが求まる。
累積和を計算しておけば、1クエリ当たり $2^6=64$ 個の値の配列参照と加減算で求められる。
各IDを桁毎にバラして $(s_1,s_2,s_3,s_4,s_5,s_6)$ の位置に重み $v$ を加算してから、各次元の累積和を取る。
この際、実際に6次元配列でやってもいいのだが、配列の入れ子は（特にPythonでは）重く・遅くなる上に、for の入れ子をいっぱい書かないといけなくなる。
高速ゼータ変換・メビウス変換のような方法で、1次元配列で管理することもできる。
zeta = [0] * 1000000
// 各IDの位置にドリンクのサイズを加算後、
for d in (次元数,今回は6):
for _id in (000000から999999まで):
if _id の d 桁目が"0"でないなら:
zeta[_id] += zeta[_id の d 桁目を1減らした数]
としていくと、累積和が取れる。
※ただし、累積和では $[L,R]$ の範囲を求める際、$Acc[R]-Acc[L-1]$ を計算する時に
$L=0$ の場合でも統一的に実装するため、先頭に $0$ を追加しておく実装もあるが、今回のこのやり方ではそれができなくなる。
などの回避策が必要となる。
Python3
以下は気合いで実装した版
from itertools import product
def solve(n, drinks, qn, queries):
acc = [[[[[[0] * 11 for _ in range(11)] for _ in range(11)] for _ in range(11)] for _ in range(11)] for _ in
range(11)]
for _id, v in drinks:
p = int(_id[0]) + 1
q = int(_id[1]) + 1
r = int(_id[2]) + 1
s = int(_id[3]) + 1
t = int(_id[4]) + 1
u = int(_id[5]) + 1
v = int(v)
acc[p][q][r][s][t][u] += v
for p, q, r, s, t in product(range(11), repeat=5):
for u in range(10):
acc[p][q][r][s][t][u + 1] += acc[p][q][r][s][t][u]
for p, q, r, s, u in product(range(11), repeat=5):
for t in range(10):
acc[p][q][r][s][t + 1][u] += acc[p][q][r][s][t][u]
for p, q, r, t, u in product(range(11), repeat=5):
for s in range(10):
acc[p][q][r][s + 1][t][u] += acc[p][q][r][s][t][u]
for p, q, s, t, u in product(range(11), repeat=5):
for r in range(10):
acc[p][q][r + 1][s][t][u] += acc[p][q][r][s][t][u]
for p, r, s, t, u in product(range(11), repeat=5):
for q in range(10):
acc[p][q + 1][r][s][t][u] += acc[p][q][r][s][t][u]
for q, r, s, t, u in product(range(11), repeat=5):
for p in range(10):
acc[p + 1][q][r][s][t][u] += acc[p][q][r][s][t][u]
bcs = [0, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 3, 2, 3, 3, 4, 1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5, 1, 2, 2, 3,
2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5, 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6]
buf = []
for x, y in queries:
p1 = int(x[0])
q1 = int(x[1])
r1 = int(x[2])
s1 = int(x[3])
t1 = int(x[4])
u1 = int(x[5])
p2 = int(y[0]) + 1
q2 = int(y[1]) + 1
r2 = int(y[2]) + 1
s2 = int(y[3]) + 1
t2 = int(y[4]) + 1
u2 = int(y[5]) + 1
if p1 >= p2 or q1 >= q2 or r1 >= r2 or s1 >= s2 or t1 >= t2 or u1 >= u2:
buf.append(0)
continue
ans = 0
for bitset in range(64):
p = p1 if (bitset & 1) else p2
q = q1 if (bitset & 2) else q2
r = r1 if (bitset & 4) else r2
s = s1 if (bitset & 8) else s2
t = t1 if (bitset & 16) else t2
u = u1 if (bitset & 32) else u2
if bcs[bitset] % 2 == 0:
ans += acc[p][q][r][s][t][u]
else:
ans -= acc[p][q][r][s][t][u]
buf.append(ans)
return buf
n = int(input())
drinks = [input().split() for _ in range(n)]
q = int(input())
queries = [input().split() for _ in range(q)]
ans = solve(n, drinks, q, queries)
print('\n'.join(map(str, ans)))
G - Sum of Mex of Mod of Linear
問題文
整数 $N,M,C,K$ と長さ $N$ の整数列 $A=(A_1,A_2,\ldots,A_N)$ が与えられます。
$Q$ 個のクエリが与えられるので、順に処理してください。
制約
$1\le N\le 2\times 10^5$
$0\le C \lt M \le 10^9$
$1\le K\le 10^9$
$0\le A_i \lt M$
$1\le Q\le 2\times 10^5$
$1\le i_q \le N$
$0\le X_q \lt M$
入力される値は全て整数
解法
Mod と Mex という2つの厄介要素が絡んできて、見た目的にイカツい。
Mexの方は要は「$A_i$ の値が連続する区間」がわかればよいと気付けると活路が見える。
$A_i$ にある値の連続区間、つまり以下のような状態を管理する。$A$ の更新にも対応できるようにしておく。
$\bmod{M}$ を考慮して、右端が $M$ の区間と、左端が $0$ の区間があったら、繋がるようにしておく。
（$0$ と $M-1$ が繋がらない状態で区間を管理しつつ、取得時に結合すれば十分）
M = 10
A = (3,3,1,4,1,9,2,0,7,6) mod M のループを考慮して
↓ [9,10) と [0,5) は繋がる
[0, 5) [6, 8) [9, 10) ------→ [6, 8) [9, 15)
すると、各区間 $[l,r)$ 内の各要素 $x$（$x=l,l+1,...,r-1$）につき、以下が言える。
$x→0$ に変換されるとき、$x+1→1$ に、$x+2→2$ に変換される。この調子で $r-1→r-1-x$ までは存在し、$r→r-x$ で値が存在しなくなるので。
x [ 9 10 11 12 13 14 ) 15
Ck+9=0 mod M となるような k に対して、
x [ 9 10 11 12 13 14 ) 15
置換後 0 1 2 3 4 5 6 ←はじめて存在しなくなるのは 6
Ck+12=0 mod M となるような k に対して、
x [ 9 10 11 12 13 14 ) 15
置換後 - - - 0 1 2 3 ←はじめて存在しなくなるのは 3
よって、以下の値を定義すると、
この $D_x$ は全てのクエリを通じて一定である。
答えは、各区間 $[l,r) $ の各 $x$ につき、$D_x \times (r-x)$ の総和となる。
区間 [6, 8) [9, 15)
x 6 7 (8) 9 10 11 12 13 14 (15)
Dx 5 5 5 5 6 5 5 6 （値の一例）
r-x 2 1 6 5 4 3 2 1
-------------------------------------
10 5 30 25 24 15 10 6 → 計 125
最初の答えは愚直に求めるとして、クエリに対しては、$A_i$ の更新に伴う影響（差分）が分かればよい。
$A_i$ の更新は、旧 $A_i$ の削除と新 $A_i$ の追加の2操作に分割してよい。
値 $x$ の削除は、$A$ に他にも $x$ が存在している場合は影響がない。
唯一の $x$ が削除される際は、削除前に $x$ が含まれていた区間を $[l,r)$ として、
「$[l, x]$ の範囲の $r-x$ が、$r-x$ ずつ小さくなる」という変化をする。
よって、累積和などで、$D_x$ の区間和を取得できるようにしておけば、差分更新できる。
追加も似た感じで、追加前に既に $x$ が存在していたら影響はない。
その他の場合、追加後に $x$ が含まれる区間を $[l,r)$ として、
「$[l, x]$ の範囲の $r-x$ が、$r-x$ ずつ大きくなる」という変化をする。
x 6 7 (8) 9 10 11 12 13 14 (15)
r-x 2 1 6 5 4 3 2 1
↓ 1（=11）の削除
r-x 2 1 2 1 0 3 2 1
↓ 8の追加
r-x 5 4 3 2 1 0 3 2 1
ただし、特殊な場合があって、「$A$ に $0～M-1$ が全て含まれる場合」はMexは常に $M$ となる。
この場合の答えは $K \cdot M$ となる。
この場合は差分更新に向かないので、上書き更新する。
そこから1つ値 $x$ が欠けたときの答えについて前計算しておけば、元の差分更新に復帰できる。
Python3
from collections import Counter
from itertools import accumulate
from math import gcd
from sortedcontainers import SortedList
class CountedRangeManager:
"""
非負整数の多重集合を管理し、個数が 1 以上の整数がなす連続区間 [l, r) を保持する
ranges: 区間の左端 l の昇順リスト（区間同士は互いに素かつ非隣接）
r_of: l -> r
cnt: 各整数の個数
"""
def __init__(self, a=()):
self.cnt = Counter()
self.ranges = SortedList()
self.r_of = {}
if a:
self.build(a)
def build(self, a):
"""非負整数列 a から構築する（既存の内容は破棄）"""
self.cnt = Counter(a)
self.ranges = SortedList()
self.r_of = {}
keys = sorted(self.cnt)
i = 0
n = len(keys)
while i < n:
j = i
while j + 1 < n and keys[j + 1] == keys[j] + 1:
j += 1
self.ranges.add(keys[i])
self.r_of[keys[i]] = keys[j] + 1
i = j + 1
def add(self, x, k=1):
"""整数 x を k 個追加する"""
if k <= 0:
return
c = self.cnt[x]
self.cnt[x] = c + k
if c > 0:
return
# x が新たに区間に含まれるようになる。左右と隣接するなら連結する
i = self.ranges.bisect_left(x) # x 以上の左端をもつ最初の区間の位置
ml = i > 0 and self.r_of[self.ranges[i - 1]] == x
mr = i < len(self.ranges) and self.ranges[i] == x + 1
if ml and mr:
r = self.ranges[i]
self.r_of[self.ranges[i - 1]] = self.r_of.pop(r)
self.ranges.remove(r)
elif ml:
self.r_of[self.ranges[i - 1]] = x + 1
elif mr:
r = self.ranges[i]
self.ranges.remove(r)
self.ranges.add(x)
self.r_of[x] = self.r_of.pop(r)
else:
self.ranges.add(x)
self.r_of[x] = x + 1
def remove(self, x, k=1):
"""整数 x を k 個削除する（個数を超えて削除しようとした場合は 0 個になる）"""
if k <= 0:
return
c = self.cnt[x]
if c == 0:
return
if c > k:
self.cnt[x] = c - k
return
del self.cnt[x]
# x が区間から外れる。x を含む区間を分割する
i = self.ranges.bisect_right(x) - 1
l = self.ranges[i]
r = self.r_of[l]
if l == x:
self.ranges.remove(l)
del self.r_of[l]
else:
self.r_of[l] = x
if x + 1 < r:
self.ranges.add(x + 1)
self.r_of[x + 1] = r
def find(self, x):
"""x を含む区間 (l, r) を返す。x の個数が 0 なら None"""
if self.cnt[x] == 0:
return None
l = self.ranges[self.ranges.bisect_right(x) - 1]
return l, self.r_of[l]
def count(self, x):
"""x の個数"""
return self.cnt[x]
def __len__(self):
return len(self.ranges)
def __iter__(self):
"""区間 (l, r) を l の昇順に列挙する"""
for l in self.ranges:
yield l, self.r_of[l]
def __repr__(self):
return ', '.join(f'[{l}, {r})' for l, r in self)
def find_loop(self, x, m):
res = self.find(x)
if res is None:
return None
if res[0] == 0:
if res[1] == m:
return res
res2 = self.find(m - 1)
if res2 is None:
return res
return res2[0], res[1] + m
if res[1] == m:
res2 = self.find(0)
if res2 is None:
return res
return res[0], res2[1] + m
return res
def solve(n, m, c, k, aaa, q, queries):
values = set(aaa)
for i, x in queries:
values.add(x)
values = sorted(values)
mapping = {x: i for i, x in enumerate(values)}
w = len(values)
def make_count():
# counts[x] := k=0,...,K-1 のうち、Ck+x = 0 mod M となるような k の個数
counts = [0] * w
g = gcd(c, m)
# Ck ≡ -x (mod M) は、g|(-x mod M) のとき k ≡ (-x/g)(C/g)^-1 (mod M/g) と一意に定まる
mg = m // g
cinv = pow(c // g, -1, mg) if mg > 1 else 0
for i, x in enumerate(values):
r = -x % m
if r % g:
continue
k0 = r // g * cinv % mg # 条件を満たす最小の k
if k0 < k:
counts[i] = (k - 1 - k0) // mg + 1
return counts
def make_gapped(counts):
# 0～m-1 のうち i だけが A に存在しない場合の答え
if w < m: # 存在する値が 0～m-1 を覆ってなければ定義不要
return []
tmp = sum(counts[i] * (m - i) for i in range(1, m))
gapped = [tmp]
for i in range(1, m):
tmp += k - counts[i] * m
gapped.append(tmp)
return gapped
counts = make_count()
gapped = make_gapped(counts)
acc_counts = [0] + list(accumulate(counts + counts))
crm = CountedRangeManager()
crm.build(aaa)
ranges = list(crm)
if len(ranges) > 1 and ranges[0][0] == 0 and ranges[-1][1] == m:
l, r = ranges.pop()
ranges[0] = (l, ranges[0][1] + m)
if len(ranges) == 1 and ranges[0] == (0, m):
ans = k * m
else:
ans = 0
for l, r in ranges:
width = r - l
vi = mapping[l]
for i in range(width):
ans += counts[(vi + i) % w] * (width - i)
def update_remove(a, ans):
if crm.count(a) > 1:
crm.remove(a)
return ans
l, r = crm.find_loop(a, m)
crm.remove(a)
if l == 0 and r == m:
return gapped[a]
vi = mapping[a]
if a < l:
a += m
vi += w
y = r - a
x = acc_counts[vi + 1] - acc_counts[mapping[l]]
return ans - x * y
def update_add(a, ans):
crm.add(a)
if crm.count(a) > 1:
return ans
l, r = crm.find_loop(a, m)
if l == 0 and r == m:
return k * m
vi = mapping[a]
if a < l:
a += m
vi += w
y = r - a
x = acc_counts[vi + 1] - acc_counts[mapping[l]]
return ans + x * y
buf = []
for i, x in queries:
i -= 1
a = aaa[i]
aaa[i] = x
ans = update_remove(a, ans)
ans = update_add(x, ans)
buf.append(ans)
return buf
n, m, c, k = list(map(int, input().split()))
aaa = list(map(int, input().split()))
q = int(input())
queries = [list(map(int, input().split())) for _ in range(q)]
ans = solve(n, m, c, k, aaa, q, queries)
print('\n'.join(map(str, ans)))
