AtCoder Beginner Contest 138 D～F問題メモ

D - Ki

問題

$N$ 頂点の木があり、$i$ 番目の辺は頂点 $A_i$ と $B_i$ を結ぶ
根は頂点1である
各頂点にはカウンターが設置されており、最初は全て0である
以下の操作を $Q$ 回行う
- $i$ 番目の操作は $p_i,x_i$ が与えられる
- $p_i$ を根とする部分木の全ての頂点のカウンターを $x_i$ を増やす
最終的な、全頂点それぞれのカウンターの数字を求めよ
$2 \le N \le 2 \times 10^5$
$1 \le Q \le 2 \times 10^5$

解法

親の情報を子に伝えながら木を根から探索する。

問題文を額面通り受け取って、毎回の操作で、部分木の全ての頂点のカウンターを更新していたら間に合わない。

木の構造上、「親に加算された数は、子孫にも必ず加算される」という性質を利用する。

    ○
    /\
  ○  ○ ←ここに加算された数は
      /\
     ○○ ←ここや
     /\
    ○○ ←ここにも必ず加算される

子の値は、「親の値」＋「自身を起点に足された値」の合計となる。

今回のように入力量が多い問題は、input()だと遅いので、sys.stdinなどを利用する。

import sys

n, q = map(int, input().split())
lines = sys.stdin.readlines()
links = [set() for _ in range(n)]
for line in lines[:n - 1]:
    a, b = map(int, line.split())
    a -= 1
    b -= 1
    links[a].add(b)
    links[b].add(a)
adds = [0] * n
for line in lines[n - 1:]:
    p, x = map(int, line.split())
    p -= 1
    adds[p] += x
ans = [-1] * n
q = [(0, 0)]
while q:
    v, a = q.pop()
    a += adds[v]
    ans[v] = a
    for u in links[v]:
        if ans[u] == -1:
            q.append((u, a))

print(*ans)

E - Strings of Impurity

問題

英小文字から成る2つの文字列 $s,t$ が与えられる
$s$ を無限回繰り返した文字列から、先頭 $i$ 文字を切り取ったものを $s'_i$ とする
$t$ が $s'_i$ の部分列となるような $i$ が存在するか判定し、存在する場合は最小の $i$ を求めよ
$1 \le |s|,|t| \le 10^5$

解法

事前計算で目次を作成する。

$s$ の各位置につき「次に文字 $a$ が出てくる位置は $b$」という目次を作っておけば、$t$ で出てくる順に目次を追っていくことで、最小の $i$ が求められる。

i     0   1   2   3   4   5   6   7
s:        a   b   c   a   d   a   b
目次 a:1 a:4 a:4 a:4 a:6 a:6
     b:2 b:2 b:7 b:7 b:7 b:7 b:7
     c:3 c:3 c:3
     d:5 d:5 d:5 d:5 d:5

t:   b d c a
  b   ------> b
  d             --------> d
  c                         --------
      ----------> c
  a                 -> a

便宜上、$i=0$ は先頭からの各文字の最初の出現位置とする。

この目次は、$s$ を後ろから見て順次、今の文字に対する位置を更新していけば作れる。 $|s|$ の上限が $10^5$、辞書のサイズが英小文字数26なので、$2.6 \times 10^6$ となりなかなか重たくはなるが、AtCoderのメモリ制限はかなり緩いので大丈夫。

こうすると、今、位置 $i$ にいて、$t$ の次の文字が $c$ だとしたとき、

目次[$i$] に、$c$ があったら、そこまでジャンプ（$i=目次[i][c]$ とする）
$c$ がなくても、次の周回であるかも知れないので、目次[0]を確認
あったら、次の周回での $i$ までジャンプ（$i=目次[0][c]$ とする）
なかったら、$s$ 全体に文字 $c$ が無いということなので、不可能

として、最後に $周回数 \times |s| +i$ が答えとなる。

def solve(s, t):
    ls = len(s)
    nxt = {}
    follow = [{} for _ in range(ls + 1)]
    for i, c in enumerate(s[::-1]):
        i = ls - i
        follow[i] = nxt.copy()
        nxt[c] = i
    follow[0] = nxt.copy()
    ans = 0
    i = 0
    for c in t:
        if c not in follow[i]:
            if c not in follow[0]:
                return -1
            ans += len(s)
            i = follow[0][c]
            continue
        i = follow[i][c]
    return ans + i


s = input()
t = input()
print(solve(s, t))

F - Coincidence

問題

整数 $L,R$ が与えられる
以下の条件を満たす整数の組 $(x,y)$ の個数を $\mod{10^9+7}$ で求めよ
- $L \le x \le y \le R$
- $y\ \% \ x = y \ XOR \ x$
$1 \le L,R \le 10^{18}$

解法

2つの数を同時に扱う桁DP。

$x,y$ の性質

まず、$y\ \% \ x = y \ XOR \ x$ の条件を考えると、2進数で表したとき

y   1  0  1  0
x      1  1  0

のように $x$ と $y$ の桁数が異なると、「XORは $y$ の最上位が必ず残るため $x$ より大きい」「剰余は必ず $x$ 未満」で、この2つが一致することは無い。

よって、桁数は必ず等しい。

ということは、商は2以上にならず、$x \le y$ のため必ず1である。つまり、割り算の余りというものの、実は引き算の結果と考えても同じことである。

$y-x = y \ XOR \ x$ となるのはどういう時か。1桁同士の対応を見ていくと、

y	x	減算	XOR	備考
0	0	0	0
0	1	1	1	より上位の桁に、繰り下がりの影響が発生
1	0	1	1
1	1	0	0

となり、基本的には一致するが、(0,1)の場合はくり下がりが発生するのでより上位の桁に影響する。ここで、下位の桁からの繰り下がりの影響を受けた場合の関係性は、

y	繰り下がり後y	x	減算	XOR	備考
0	1	0	1	0	繰り下がり継続
0	1	1	0	1	繰り下がり継続
1	0	0	0	1
1	0	1	1	0	繰り下がり継続

となり、くり下がりが継続するかどうか以前に、今の桁で全ての場合で一致しなくなる。つまり、くり下がりが1箇所でも発生してはいけないということになる。

言い換えると、$y$ で“0”である桁では、$x$ も“0”でないといけない。このような関係を、bitの文脈では「$x$ は $y$ のsubset」という。

y  110010110010
x  100000110000

数え上げ

そのような $x,y$ の組を、$L～R$ の範囲で求める。桁DPと予想は付くが、どのように状態を分ければ良いか難しい。

ここは、$x,y$ 2つの数をセットで1つの状態と捉える。

よく、上限が決められた桁DPでは「上から $i$ 桁目までが上限と一致し、下位の桁の自由度が制限されている場合」と「上限より小さいことが確定し、下位の桁は自由に決められる状態」で分けて数えるが、今回はそれを $L$ の下限にも適用する感じ。

$DP[i][k=0/1/2/3]=$ 上から $i$ 桁目までで、以下の場合の $(x,y)$ の組の数
- $k=0$: $y$ が上限ギリギリ、$x$ が下限ギリギリ
- $k=1$: $y$ が上限ギリギリ、$x$ は自由
- $k=2$: $y,x$ ともに自由
- $k=3$: $y$ は自由、$x$ が下限ギリギリ

ここからさらに$x,y$の桁数を考慮するとこんがらがるので、$x,y$の桁数は固定とし、考慮すべき桁数分だけループを回す。

つまり、$L=101,R=10110$ のように桁数が違う場合は、以下のように別々に求めて、合計する。

桁数3: L=  101  R=  111
桁数4: L= 1000  R= 1111
桁数5: L=10000  R=10110

（まとめて1回でやろうと思えば、「ここまでの桁がx,yとも全て0フラグ」を持ってその状態も管理すれば可能）

DPの初期状態を考える。まず、先頭桁は両者必ず“1”である必要があり、1桁目まで考慮した $(y,x)$ の組は (1,1) の1通りしかない。この状態は $k=0$（$y,x$ ともにギリギリ）に相当するため、以下で初期化する。

$DP[0] = [1, 0, 0, 0]$

次に、$i-1$ からの遷移を考える。

例えば $i-1$ 桁目まで考慮された $(y,x)$ の具体的な値を適当に1つ考える。（例えば5桁目までで (11101, 11001) など）

このそれぞれの末尾に0か1をくっつけて、$i$ 桁目の状態に遷移したい。くっつけ方は、(y,x)←(0,0)(1,0)(1,1) の3通り。

ここから「$k$（$y$ がギリギリか、$x$ がギリギリか）」「$R_i$ が'0'か'1'か」「$L_i$ が'0'か'1'か」「くっつける数は(0,0)(1,0)(1,1)のどれか」の、4*2*2*3=48通りについて、考えていく。

$R_i$ が '0' の時、$y$ が上限ギリギリの場合は、'1'はくっつけられない
$L_i$ が '1' の時、$x$ が下限ギリギリの場合は、'0'はくっつけられない

ことに注意。（遷移不能な場合は'x'で表す）

k=0（yギリギリ, xギリギリ）
Ri,Li       (0,0)   (1,0)   (0,1)   (1,1)
yに付加    1 1 0   1 1 0   1 1 0   1 1 0
xに付加    1 0 0   1 0 0   1 0 0   1 0 0
遷移するk  x x 0   1 0 3   x x x   0 x x

k=1（yギリギリ, x自由）
Ri,Li       (0,?)   (1,?)
yに付加    1 1 0   1 1 0
xに付加    1 0 0   1 0 0
遷移するk  x x 1   1 1 2

k=2（y自由, x自由）
Ri,Li       (?,?)
yに付加    1 1 0
xに付加    1 0 0
遷移するk  2 2 2
  
k=3（y自由, xギリギリ）
Ri,Li       (?,0)   (?,1)
yに付加    1 1 0   1 1 0
xに付加    1 0 0   1 0 0
遷移するk  2 3 3   3 x x

これを頑張って実装すると、通る。

def count(lb, rb):
    assert lb[0] == '1'
    assert rb[0] == '1'
    assert len(lb) == len(rb)
    dp = [1, 0, 0, 0]
    for lc, rc in zip(lb[1:], rb[1:]):
        ndp = [dp[0], 0, 0, 0]
        if rc == '0':
            ndp[1] += dp[1]
            if lc == '1':
                ndp[0] = 0
        else:
            ndp[1] += dp[1] * 2
            ndp[2] += dp[1]
            if lc == '0':
                ndp[1] += dp[0]
                ndp[3] += dp[0]
        if lc == '0':
            ndp[2] += dp[3]
            ndp[3] += dp[3] * 2
        else:
            ndp[3] += dp[3]
        ndp[2] += dp[2] * 3
        dp = ndp
    return sum(dp)


l, r = map(int, input().split())
lb = bin(l)[2:]
rb = bin(r)[2:]
ld = len(lb)
rd = len(rb)
ans = 0
MOD = 10 ** 9 + 7
for d in range(ld, rd + 1):
    tlb = lb if d == ld else '1' + '0' * (d - 1)
    trb = rb if d == rd else '1' * d
    ans = (ans + count(tlb, trb)) % MOD
print(ans)