差分

このページの2つのバージョン間の差分を表示します。

この比較画面へのリンク

両方とも前のリビジョン前のリビジョン
次のリビジョン
前のリビジョン
programming_algorithm:contest_history:atcoder:2019:0609_abc129 [2019/06/12] – [解法] ikatakosprogramming_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, 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)) 
 +</sxh>
  
  
行 189: 行 223:
 さて、ここで、線形の漸化式は行列に変換できる。 さて、ここで、線形の漸化式は行列に変換できる。
 つまり、以下のように表せる。 つまり、以下のように表せる。
 +
 +\[
 +\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.
 +\]
  
 \[ \[
programming_algorithm/contest_history/atcoder/2019/0609_abc129.txt · 最終更新: 2019/06/12 by ikatakos
CC Attribution 4.0 International
Driven by DokuWiki Recent changes RSS feed Valid CSS Valid XHTML 1.0