目次
AtCoder Beginner Contest 158 D,E,F問題メモ
D - String Formation
問題
- 英小文字から成る文字列 $S$ がある
- この $S$ に $Q$ 回の操作を加えて新しい文字列を作る
- $i$ 回目の操作は、以下の2種類からなる
1:- 文字列 $S$ を反転する
2 Fi Ci:- $F_i=1$ のとき、$S$ の先頭に英小文字 $C_i$ を追加する
- $F_i=2$ のとき、$S$ の末尾に英小文字 $C_i$ を追加する
- 最終的にできる文字列を答えよ
- $1 \le |S| \le 10^5$
- $1 \le Q \le 2 \times 10^5$
解法
だいたいその通りにやるだけ、なんだけど、文字列の反転操作や、末尾以外への追加は重たいので、それをなるべく避けたコードを書く。
「今、反転してるか？」をフラグで持ち、実際に反転はしないで処理を分岐させるとよい。
文字列処理のパフォーマンスは、わりと言語に依るところも大きいのかも。Pythonでは、（細かなケースは分からないが、概して）PyPyよりPythonの方が速い。
import sys
s = input()
q = int(input())
rev = 0
append_front_rev = ''
append_rear = ''
for line in sys.stdin:
q = line.strip()
if q == '1':
rev ^= 1
else:
_, f, c = q.split()
if f == '1':
if rev == 0:
append_front_rev += c
else:
append_rear += c
else:
if rev == 0:
append_rear += c
else:
append_front_rev += c
s = append_front_rev[::-1] + s + append_rear
if rev:
s = s[::-1]
print(s)
E - Divisible Substring
問題
'0'～'9'までの数字からなる長さ $N$ の文字列 $S$ がある- $S$ から連続した部分文字列を切り出す方法は $\dfrac{N(N+1)}{2}$ 通りある
- そのうち素数 $P$ の倍数となっているものの個数を求めよ
- $1 \le N \le 2 \times 10^5$
- $2 \le P \lt 10000$
解法
桁DP……っぽさはあるけど、方向が大事。下から計算するとわかりやすい。
$i$ 桁目以降を10進表記の数字と見なしたものを、$T_i$ とする。
i 0 1 2 3 4 S 1 3 0 0 3 T1 3 0 0 3 T3 0 3
これを使って部分文字列 $S[l,r)$ を数式で表すと、$\dfrac{T_l-T_r}{10^{r-l}}$ となる。これが $P$ の倍数となるには、どのような条件が必要か？
$10=2 \times 5$ なので、$P$ がこの2つの素数の場合はちょっと場合分けが必要だが、いずれも簡単に判定できる。
P=2の場合
末尾が偶数なら2の倍数である。$i$ 番目に偶数が出てきたら、そこを右端とする部分文字列は $i+1$ 個作れる。
i 0 1 2 3 4 S 1 3 0 0 3 [ [ [ ] i=2を右端とする部分文字列は、130, 30, 0 の3つ作れる
よって、$S$ を先頭から見ていって、偶数ならその位置に応じた部分文字列数を適宜加えていけばよい。
P=5の場合
末尾が0か5なら5の倍数である。あとは $P=2$ と同じ。
その他の場合
$\dfrac{T_l-T_r}{10^{r-l}}$ が $P$ の倍数であるためには、$10^{r-l}$ と素数 $P$ は互いに素なので、 $T_l-T_r$ が $P$ の倍数であればよい。
つまり、下から $T_i \mod{P}$ を計算しておき、値が等しくなる2箇所を $l,r$ とすると、上手くいく。
P=7
i 0 1 2 3 4 (5)
-------------------------
S 1 3 0 0 3
Ti % P 4 0 3 3 3 0 （末尾に便宜的に0を追加）
[l, r) = [1, 5) 3003
[2, 3) 0
[2, 4) 00
[3, 4) 0
この4つが P=7 の倍数となっている
個数を数えるには、全ての $T_i \mod{P}$ を計算した後、各数字が何回出てくるかをカウントする。
ある数字が $c$ 回出てきたら、その数字の位置から2箇所を選ぶ組み合わせは $\dfrac{c(c-1)}{2}$ 個あるので、これを足し合わせればよい。
4: 1回 0個 0: 2回 → 2 * (2-1) / 2 = 1個 3: 3回 → 3 * (3-1) / 2 = 3個 → 合計4個
from collections import defaultdict
def solve2(s):
ans = 0
for i, c in enumerate(s):
if c in '02468':
ans += i + 1
return ans
def solve5(s):
ans = 0
for i, c in enumerate(s):
if c in '05':
ans += i + 1
return ans
def solve_other(s, p):
reminders = defaultdict(lambda: 0)
tmp = 0
mul = 1
for c in s[::-1]:
c = int(c)
tmp = (tmp + c * mul) % p
mul = mul * 10 % p
reminders[tmp] += 1
reminders[0] += 1
ans = 0
for r, cnt in reminders.items():
ans += cnt * (cnt - 1) // 2
return ans
n, p = list(map(int, input().split()))
s = input()
if p == 2:
print(solve2(s))
elif p == 5:
print(solve5(s))
else:
print(solve_other(s, p))
F - Removing Robots
問題
- 数直線上に $N$ 個のロボットがある
- ロボット $i$ ははじめ座標 $X_i$ に位置する
- 起動すると $D_i$ だけ正の方向に移動し、移動を終えると消滅する
- 移動途中に他の停止中のロボットと同じ座標に来ると、そのロボットを起動する（移動は継続する）
- 起動されたロボットも同じように移動を開始し、他のロボットと同じ座標に来るとそいつを起動する
- ちょうど移動終了で接触する（$X_i+D_i=X_j$）時、ロボット $i$ はロボット $j$ を起動しない
- 今、以下の操作を好きなだけ繰り返す（1回も行わないことも可能）
- ロボットを1つ起動する
- 移動中のロボットがいなくなるまで待つ
- 操作を繰り返した後、数直線上に残るロボットの組み合わせとして考えられるパターン数を $\mod{998244353}$ で求めよ
- $1 \le N \le 2 \times 10^5$
- $-10^9 \le X_i \le 10^9$
- $1 \le D_i \le 10^9$
解法
「ロボット $i$ を起動したら、右側に連続するここまでのロボットが連鎖的に起動され、消滅する」というのが各ロボットにつきある。
言い換えると、連鎖的に起動する範囲内のロボットを残したまま、ロボット $i$ を消滅させる、ということはできない。
（例）ロボットの初期位置と影響範囲
1 2 3 4 5 6 7 8 9
|-----------| |-| |---| |-|
|-| |-|
|--------|
|-|
|---|
ロボット1は、起動すると2,3,4を起動し、さらに3が5を起動するため、2～5も連鎖的に消滅する。つまり、1を消滅させつつ2とか5を残すことはできない。
1から右のロボットのみに着目した場合の数は、「1を残した場合の数」+「1を起動させた場合の数」となるので、この2つに分けて考える。
- 1を残した場合の数
- そのまま「2から右のロボットのみに着目した場合の数」となる
- 1を起動させた場合の数
- 1を起動させることで消滅しない、最も左のロボットを $k$（例では6）とすると、「$k$ から右のロボットのみに着目した場合の数」となる
よって、以下のDPを定義し、右から順に埋めていくとよい。
- $DP[i]=i$ から右のロボットのみに注目したときの場合の数
ここで、ロボット $i$ を起動したら、どこまでのロボットが消滅するのか？を、ある程度高速に求める必要がある。
直接的に起動するロボットは $X$ を昇順に並べ $X_i+D_i$ を二分探索するなどで求められるが、 間接的に起動したロボットを含めるとどこまで行くか？ はなかなか難しそうに見える。
例では、1が直接的に起動するのは4までだが、実際は5まで起動される。 しかし5を起動させるのは3であり、それを調べるには、端の4だけを調べるのでは不足で、2～4を全て調べて最大値を得なければならない。
実装するには、セグメント木で「ロボット $i$ を起動すると、ロボット $p_i$ まで消滅する」 という情報を持てばよい。
自身が直接的に起動するロボット番号の右端 $j$ を二分探索で見つけ、$p_{i+1}～p_j$ の中で最大の $p_k$ を見つける。 $DP[p_k+1]$ が、$i$ を起動した場合に $DP[i]$ に加算される場合の数となる。 1点更新、区間Max取得のセグメント木で実装可能。
計算量は、$O(N \log{N})$ となる。
import sys
from bisect import bisect_left
from operator import itemgetter
class SegTreeMax:
"""
以下のクエリを処理する
1.update: i番目の値をxに更新する
2.get_min: 区間[l, r)の最小値を得る
"""
def __init__(self, n, INF):
"""
:param n: 要素数
:param INF: 初期値（入りうる要素より十分に大きな数）
"""
n2 = 1 << (n - 1).bit_length()
self.offset = n2
self.tree = [INF] * (n2 << 1)
self.INF = INF
def initialize(self, arr):
for i, v in enumerate(arr, start=self.offset):
self.tree[i] = v
for i in range(self.offset - 1, 0, -1):
j = i << 1
self.tree[i] = max(self.tree[j], self.tree[j + 1])
def update(self, i, x):
"""
i番目の値をxに更新
:param i: index(0-indexed)
:param x: update value
"""
i += self.offset
self.tree[i] = x
while i > 1:
y = self.tree[i ^ 1]
if y >= x:
break
i >>= 1
self.tree[i] = x
def get_max(self, a, b):
"""
[a, b)の最大値を得る
:param a: index(0-indexed)
:param b: index(0-indexed)
"""
result = self.INF
l = a + self.offset
r = b + self.offset
while l < r:
if r & 1:
result = max(result, self.tree[r - 1])
if l & 1:
result = max(result, self.tree[l])
l += 1
l >>= 1
r >>= 1
return result
n, *xd = map(int, sys.stdin.buffer.read().split())
MOD = 998244353
xd = sorted(zip(xd[0::2], xd[1::2]))
xxx = list(map(itemgetter(0), xd))
ans = [0] * (n + 1)
skip = list(range(1, n + 1))
ans[n] = 1
sgt = SegTreeMax(n + 1, 0)
sgt.initialize(list(range(1, n + 2)))
for i in range(n - 1, -1, -1):
x, d = xd[i]
r = x + d
j = bisect_left(xxx, r)
k = sgt.get_max(i, j)
ans[i] = (ans[i + 1] + ans[k]) % MOD
sgt.update(i, k)
print(ans[0])
スタックで管理してもよい。
スタックには、右から処理して $i$ まで処理した上で、「現時点で他のどのロボットによっても起動されることはない」ロボットの、座標と番号を積んでいく。
1 2 3 4 5 6 7 8 9
|-----------| |-| |---| |-|
|-| |-|
|--------|
|-|
|---|
4まで処理したら、スタックは $[9, 7, 6, 5, 4]$ となっている。
次、3を処理するとき、$X_3+D_3$ より $X_i$ が小さいものは、末尾からpopしていく。
そうして残ったスタックの末尾要素（6）が、3を起動したときに残る左端のロボット番号となる。
そして自身（3）を積んで、次のロボットに進む。この時点でスタックは $[9,7,6,3]$ となる。
セグメント木より問題特化な解法だが、こちらの方が高速で計算量は $O(N)$ となる。
import sys
from operator import itemgetter
n, *xd = map(int, sys.stdin.buffer.read().split())
MOD = 998244353
xd = sorted(zip(xd[0::2], xd[1::2]))
xxx = list(map(itemgetter(0), xd)) + [10 ** 10]
ans = [0] * n + [1]
stack = [n]
for i in range(n - 1, -1, -1):
x, d = xd[i]
r = x + d
while r > xxx[stack[-1]]:
stack.pop()
ans[i] = (ans[i + 1] + ans[stack[-1]]) % MOD
stack.append(i)
print(ans[0])
