差分
このページの2つのバージョン間の差分を表示します。
両方とも前のリビジョン前のリビジョン次のリビジョン | 前のリビジョン | ||
programming_algorithm:contest_history:atcoder:2019:0609_abc129 [2019/06/12] – [解法] ikatakos | programming_algorithm:contest_history:atcoder:2019:0609_abc129 [2019/06/12] (現在) – [解法] ikatakos | ||
---|---|---|---|
行 79: | 行 79: | ||
numpyを上手く使うと、Pythonでも通る。ただ、上手く使うよう考える必要がある。特にNumPyでも添字アクセスは遅いので最小限にとどめたい。 | numpyを上手く使うと、Pythonでも通る。ただ、上手く使うよう考える必要がある。特にNumPyでも添字アクセスは遅いので最小限にとどめたい。 | ||
- | 外周を壁で覆って「左の一番近い壁のindex」と「右の一番近い壁のindex」はnumpy.ufunc.accumulateで求められるので、その差分を取ることで横方向の照らされるマス数はわかる。 | + | 外周も壁で覆って「左の一番近い壁の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)がわかる | ||
+ | |||
+ | これを縦方向でも行い、足し合わせることで、上下左右に照らされるマス数を求めることができる。 | ||
+ | |||
+ | <sxh python> | ||
+ | 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, | ||
+ | ui = np.maximum.accumulate(field_idx, | ||
+ | |||
+ | field_idx += (field ^ 1) * field.size | ||
+ | ri = np.fliplr(np.minimum.accumulate(np.fliplr(field_idx), | ||
+ | di = np.flipud(np.minimum.accumulate(np.flipud(field_idx), | ||
+ | return (ri - li + (di - ui) // field.shape[1]).max() - 3 | ||
+ | |||
+ | |||
+ | h, w = list(map(int, | ||
+ | field = np.ones((h + 2, w + 2), dtype=np.int32) | ||
+ | field[1:h + 1, 1:w + 1] = [[c == '#' | ||
+ | print(solve(field)) | ||
+ | </ | ||
行 181: | 行 215: | ||
$L=1$ だったら、$S_1=A$ である。ここで、$S_k$ は初項・公差の条件が同じで $L=k$ の時の $S$ とする。 | $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=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桁の場合) | $L=3$ なら、$S_3=10^6A+10^3(A+B)+(A+2B)$ と表現できる。($A+2B$ も3桁の場合) | ||
行 189: | 行 223: | ||
さて、ここで、線形の漸化式は行列に変換できる。 | さて、ここで、線形の漸化式は行列に変換できる。 | ||
つまり、以下のように表せる。 | つまり、以下のように表せる。 | ||
+ | |||
+ | \[ | ||
+ | \left \{ | ||
+ | \begin{align} | ||
+ | S_i &=& 10^d \times S_{i-1} &+& 1 \times a_{i-1} &+& 0 \times 1 \\ | ||
+ | a_i & | ||
+ | 1 & | ||
+ | \end{align} | ||
+ | \right. | ||
+ | \] | ||
\[ | \[ | ||
行 284: | 行 328: | ||
first_d = len(str(a)) | first_d = len(str(a)) | ||
- | tail = a + b * (l - 1) | ||
lo = -1 # d桁未満となる最後の項が何番目か | lo = -1 # d桁未満となる最後の項が何番目か |