差分

この文書の現在のバージョンと選択したバージョンの差分を表示します。

この比較画面にリンクする

両方とも前のリビジョン 前のリビジョン
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,​ 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>​
  
  
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