目次
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)
