−目次

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

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

AtCoder Beginner Contest 158

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])

            

        
      