目次
AtCoder Beginner Contest 129 D,E,F 問題メモ
D - Lamp
問題
- $H \times W$ マスの盤面
- 各マスは '.'なら床、'#'なら壁
- 床マスの1つを選んでライトを置く
- ライトは上下左右4方向を一直線に照らし、壁に当たるとそこで止まる
- ライトを置かれているマス自体も照らされる。壁マスは照らされない
- 照らされるマス数の最大値を求めよ
- $1 \le H,W \le 2000$
ペンシルパズル誌ニコリの「美術館」が似たようなルールである。
解法
各マスから4方向最大何マス伸ばせるかを調べ、4方向分足し合わせて最大を調べる。
Pythonだと遅いのでPyPyを使うが、PyPyを使う場合でもいくつかの点に気をつけないと、速度が上がらないことがある。
今回の場合、特に効いてくるのはイテレート関数で、以下に気をつける。
- enumerate 使うより、rangeで回して添字アクセスした方が速い
- zipで結合するより、rangeで回してそれぞれに添字アクセスした方が速い
Pythonならfor回すよりこういう関数を上手く使った方が速いのだが、PyPyの場合は逆転する。 また、PyPyのJITはあまり複雑な書き方をすると最適化されにくくなるので、出来るだけシンプルな構文で書いた方がよい。
あと、Pythonよりましとはいえリストへの添字アクセスは速くは無いので、二重ループの一重目では二番目のループで共通な変数はキャッシュしておく等で、わずかに速くなる。 まぁこの問題ではそこまで面倒なことをしなくても素直に書きさえすればPyPyで問題なく通る。
import sys
h, w = list(map(int, input().split()))
field = [line.rstrip() for line in sys.stdin]
l = [[0] * (w + 2) for _ in [0] * (h + 2)]
r = [[0] * (w + 2) for _ in [0] * (h + 2)]
u = [[0] * (w + 2) for _ in [0] * (h + 2)]
d = [[0] * (w + 2) for _ in [0] * (h + 2)]
for i in range(1, h + 1):
fi = field[i - 1]
l_tmp = 0
li = l[i]
for j in range(1, w + 1):
c = fi[j - 1]
u[i][j] = u[i - 1][j] + 1 if c == '.' else 0
li[j] = l_tmp = l_tmp + 1 if c == '.' else 0
for i in range(h, 0, -1):
fi = field[i - 1]
r_tmp = 0
ri = r[i]
for j in range(w, 0, -1):
c = fi[j - 1]
d[i][j] = d[i + 1][j] + 1 if c == '.' else 0
ri[j] = r_tmp = r_tmp + 1 if c == '.' else 0
ans = 0
for i in range(1, h + 1):
li, ri, ui, di = l[i], r[i], u[i], d[i]
ans = max(ans, max(li[j] + ri[j] + ui[j] + di[j] for j in range(1, w + 1)))
print(ans - 3)
numpyを上手く使うと、Pythonでも通る。ただ、上手く使うよう考える必要がある。特にNumPyでも添字アクセスは遅いので最小限にとどめたい。
外周も壁で覆って「左の一番近い壁のindex」と「右の一番近い壁のindex」はnumpy.ufunc.accumulateで求められるので、その差分を取ることで横方向の照らされるマス数はわかる。
0 1 2 3 4 5 6 7 8 index # . # . . # . . # 盤面の任意の1行 0 0 2 0 0 5 0 0 8 壁マスのindexを残し、床マスを0にする 0 0 2 2 2 5 5 5 8 左から累積maxを取ると、各マスの「左の一番近い壁」がわかる 0 99 2 99 99 5 99 99 8 壁マスのindexを残し、床マスを適当な大きい数字にする 0 2 2 5 5 5 8 8 8 右から累積minを取ると、各マスの「右の一番近い壁」がわかる 0 2 0 3 3 0 3 3 0 差分を取るとそのマスにライトを置いたときに横方向に照らされるマス数（+1）がわかる
これを縦方向でも行い、足し合わせることで、上下左右に照らされるマス数を求めることができる。
import sys
import numpy as np
def solve(field):
idx = np.arange(field.size).reshape(field.shape)
field_idx = field * idx
li = np.maximum.accumulate(field_idx, axis=1)
ui = np.maximum.accumulate(field_idx, axis=0)
field_idx += (field ^ 1) * field.size
ri = np.fliplr(np.minimum.accumulate(np.fliplr(field_idx), axis=1))
di = np.flipud(np.minimum.accumulate(np.flipud(field_idx), axis=0))
return (ri - li + (di - ui) // field.shape[1]).max() - 3
h, w = list(map(int, input().split()))
field = np.ones((h + 2, w + 2), dtype=np.int32)
field[1:h + 1, 1:w + 1] = [[c == '#' for c in line.rstrip()] for line in sys.stdin]
print(solve(field))
E - Sum Equals Xor
問題
- 正整数 $L$ が二進数表記で与えられるので、以下の条件を満たす非負整数 $(a,b)$ の組の個数を $\mod{10^9+7}$ で求めよ
- $a+b \le L$
- $a+b=a \ XOR \ b$
- $1 \le L \le 2^{10001}$
解法
いわゆる桁DPの典型とも言える問題。
$a+b=a \ XOR \ b$ という条件は「2進数表記で両方が共に1である桁は無い」と言い換えられる。 足し算とXORは、両方の桁が共に1である場合のみ、繰り上がりの有無で異なってくる。 （そして加算は常にXOR以上なので、上の桁以降でこの違いを吸収する術は無い）
| $a$ | $b$ | $a+b$ | $a \ XOR \ b$ |
|---|---|---|---|
| 0 | 0 | 0 | 0 |
| 0 | 1 | 1 | 1 |
| 1 | 0 | 1 | 1 |
| 1 | 1 | 10 | 0 |
2つの変数でDPを管理する。上の桁から順に見て、
$dp1[i]=$ 上位 $i$ 桁目までだけを考えて、和が $L$ と一致している中での2数の組の個数。つまり以降の桁は、$L$ を超えないようにする必要がある。
$dp0[i]=$ 上位 $i$ 桁目までだけを考えて、和が $L$ より小さくなっている2数の組の個数。つまりもう $L$ を超えることは無いので、以降の桁は（他の条件を満たしていれば）どうなっていてもよい。
L 1 0 1 1 0 0 0 1 a+b 1 0 1 => dp1 a+b 1 0 0 => dp0
$L$ の今見ている桁（上から $i$ 桁目）が0の場合、
- dp1は $(0,0)$ を選ぶしか無く、そのまま$dp1[i]=dp1[i-1]$
- dp0は何を選んでもよく、$(0,0),(0,1),(1,0)$ の3通り。$dp0[i] = 3 \times dp0[i-1]$
$L$ が1の場合、
- dp1は、dp1を維持するには $(0,1),(1,0)$ のいずれかをとる。$dp1[i]=2 \times dp1[i-1]$
- dp0は $(0,0),(0,1),(1,0)$ の3通りに加え、dp1で $(0,0)$ となってdp0に遷移してきたものを合計する。$dp0[i] = 3 \times dp0[i-1] + dp1[i-1]$
l = input()
dp0 = 0
dp1 = 1
MOD = 10 ** 9 + 7
for c in l:
if c == '0':
dp0 = dp0 * 3 % MOD
else:
dp0 = (dp0 * 3 + dp1) % MOD
dp1 = dp1 * 2 % MOD
print((dp0 + dp1) % MOD)
F - Takahashi's Basics in Education and Learning
問題
- 初項 $A$ 公差 $B$ の $L$ 項の等差数列
- 頭に0の無い十進数で表記して、順に文字列として一列に並べる
- これを1つの数字として解釈したとき、$M$ で割った余りを求めよ
- $1 \le L,A,B \lt 10^{18}$
- $2 \le M \le 10^9$
- 数列の全ての項は $10^{18}$ 未満
例
初項 3 公差 4 項数 5 割る数 107 ↓ 数列 3 7 11 15 19 並べる 37111519 あまり 37111519 % 107 = 67
解法
$M$ で割る前の連結して出来上がる数を、$S$ とする。
$S$ は、数式としてはどうにもこうにも表しにくい。「数列の全ての項は $10^{18}$ 未満」というわざとらしい制約を使えないか考えてみる。
$L,A,B$ の範囲がえげつないが、これらが実際に全て最大値を取ったら余裕で項が $10^{18}$ 超えちゃうので、 実際は $A$ がでかかったら $L,B$ は小さいし、$L$ がでかかったら $A,B$ は小さい。 この制約を設けると $L,A,B$ の範囲が実際にかなり絞られるため、何かしら意味があると推測する。
桁数で項を分類すると、たかだか18分類しかないし、漸化式としても表しやすくなることを利用する。
$A$ がたとえば3桁だったとする。そして、第 $i$ 項まで3桁が続くとする。
$L=1$ だったら、$S_1=A$ である。ここで、$S_k$ は初項・公差の条件が同じで $L=k$ の時の $S$ とする。
$L=2$ なら $S_2$ は $(A)(A+B)$ をこの順に繋げた数だが、$A+B$ も3桁ならこれは $10^3A + (A+B)$ と数式で表現できる。
$L=3$ なら、$S_3=10^6A+10^3(A+B)+(A+2B)$ と表現できる。（$A+2B$ も3桁の場合）
つまり、桁数が同じ限り、$S_i = 10^dS_{i-1}+a_{i-1}$ という漸化式で表せる。（$S_0=0,a_0=A$ とする）
さて、ここで、線形の漸化式は行列に変換できる。 つまり、以下のように表せる。
\[ \left \{ \begin{align} S_i &=& 10^d \times S_{i-1} &+& 1 \times a_{i-1} &+& 0 \times 1 \\ a_i &=& 0 \times S_{i-1} &+& 1 \times a_{i-1} &+& B \times 1 \\ 1 &=& 0 \times S_{i-1} &+& 0 \times a_{i-1} &+& 1 \times 1 \end{align} \right. \]
\[ \left( \begin{array}{ccc} S_i & a_i & 1 \end{array} \right) = \left( \begin{array}{ccc} S_{i-1} & a_{i-1} & 1 \\ \end{array} \right) \left( \begin{array}{ccc} 10^d & 0 & 0 \\ 1 & 1 & 0 \\ 0 & B & 1 \end{array} \right) \]
すると、これは再帰的に置換すると、行列累乗の形になる。
\[ \left( \begin{array}{ccc} S_i & a_i & 1 \end{array} \right) = \left( \begin{array}{ccc} S_0 & a_0 & 1 \\ \end{array} \right) \left( \begin{array}{ccc} 10^d & 0 & 0 \\ 1 & 1 & 0 \\ 0 & B & 1 \end{array} \right)^{桁数がdである項の数} \]
行列計算は結合則を満たすので、累乗の方を先に計算してしまってよい。累乗はダブリングを使えば $O(\log{指数})$ で高速に求められる。
さて、桁上がりを考える。第 $i+1$ 項目ではじめて桁数が $d$ になり、第 $j$ 項目まで同じ桁数が続くとする。
とは言っても、これも係数行列の $d$ が変わるだけで、上とほとんど変わらない。
桁が $d$ 未満である第 $i$ 項目までは計算済みとする。つまり、$\left( \begin{array}{ccc} S_i & a_i & 1 \end{array} \right)$ は計算済みとすると、
\[ \left( \begin{array}{ccc} S_j & a_j & 1 \end{array} \right) = \left( \begin{array}{ccc} S_i & a_i & 1 \\ \end{array} \right) \left( \begin{array}{ccc} 10^d & 0 & 0 \\ 1 & 1 & 0 \\ 0 & B & 1 \end{array} \right)^{桁数がdである項の数} \]
で、$j$ まで求められる。
これを、$d$ の小さい方から順に、適宜 $M$ で割りながら $L$ 項目まで計算すればよい。計算量は $O(\log{L})$ となる。
Pythonでは、numpy.dot()を使うのが楽。ただしdtypeにint64を指定し、1回ごとに $M$ で割らないとオーバーフローする。
import numpy as np
def exp_np(a, e, m):
r = np.identity(a.shape[0], dtype=np.int64)
t = a.copy()
while e:
if e % 2:
r = np.dot(r, t) % m
t = np.dot(t, t) % m
e >>= 1
return r
l, a, b, m = map(int, input().split())
first_d = len(str(a))
lo = -1 # d桁未満となる最後の項が何番目か
state = np.array([[0, a % m, 1]])
for d in range(first_d, 19):
hi = min((10 ** d - 1 - a) // b, l - 1) # d桁となる最後の項が何番目か
cnt = hi - lo
coe = np.array([
[pow(10, d, m), 0, 0],
[1, 1, 0],
[0, b % m, 1]
], dtype=np.int64)
coe = exp_np(coe, cnt, m)
state = np.dot(state, coe) % m
lo = hi
if hi == l - 1:
break
print(state[0][0])
