AtCoder Beginner Contest 129DをPythonで解く

今回は、AtCoder Beginner Contest 129D
を解いていきたいと思います。

問題文

縦H行横W列のグリッドが与えられます。このグリッドのうち、いくつかのマスには障害物が存在します。すぬけ君は、障害物のないマスのうち一つを選び、そのマスに明かりを設置しようとしています。 設置されたマスから、上下左右の四方向にまっすぐに光線が伸びます。それぞれの方向について、最初に障害物が存在するマスにぶつかる、もしくはグリッドの端にぶつかる手前のマスまで照らされます。明かりを設置したマスも照らされますが、障害物が存在するマスは照らされません。
すぬけ君は明かりによって照らされるマスの個数を最大化したいです。
H個の長さWの文字列 Si(1≤i≤H)が与えられます。Siの j文字目 (1≤j≤W) が # のとき、グリッドの上からi行目で左からj列目のマスには障害物があり、 . のときは障害物がありません。
照らされるマスの個数の最大値を求めてください。

こう考えた

• numpyを使う
• 二次元配列に[h,w]を入力する空の配列を作る。
• マス目毎に上、下、右、左を確認するコードを作成し、h,wに格納する。
• max()で出力

書いたコード

L=[list(input() )for i in range(H)]
L = np.array(L)
print(L)
M=[]
for h in range(H):
  for w in range(W):
    if L[h][w]=="#":
      M.append([0,0])
    else:
      R=1
      for r in range(W-w-1):
        if L[h][w+r+1]==".":
          R=R+1
        else:
          break
      for r in range(w-1):
        if L[h][w-r-1]=="." and w-r-1>=0:
          R=R+1
        else:
          break
      M.append(R)
print(M)

🐍ここまで書いたけど知識不足で書けない。。

コードを読んでみる

from numpy import*
h,*s=open(0)
h,w=int64(h.split())
r=range
s=array([list(t[:-1])for t in s])
a,b,c,d=eval('zeros((h,w),"i"),'*4)
for i in r(w):
    a[:,i]=-~a[:,i-1]*(s[:,i]>'#')
    b[:,~i]=-~b[:,-i]*(s[:,~i]>'#')
for i in r(h):
    c[i,:]=-~c[i-1,:]*(s[i,:]>'#')
    d[~i,:]=-~d[-i,:]*(s[~i,:]>'#')
print(int((a+b+c+d).max())-3)

3行目まで

h,*s=open(0)
print(h)
print(s)
h,w=int64(h.split())
print(h)
print(w)

🐍とりあえず出力確認や

4 6
['#..#..\n', '.....#\n', '....#.\n', '#.#...']
4
6

🐍なるほど

r=range

🐍なるほど後でfor i in range()が何度か出てくるからここで定義してるねんな。

s=array([list(t[:-1])for t in s])

🐍numpyのarrayに変換してるねんな。なんで[list(t[:-1])なんやろ？

[['#', '.', '.', '#', '.', '.'] ['.', '.', '.', '.', '.', '#']
 ['.', '.', '.', '.', '#', '.'] ['#', '.', '#', '.', '.']]

['#..#..\n' '.....#\n' '....#.\n' '#.#...']

🐍1次元配列なるし、改行も含まれてまうねんな。

a,b,c,d=eval('zeros((h,w),"i"),'*4)

🐍 eval は第1引数を式として評価してるから'zeros((h,w),"i"),'までが今回は引数。zerosは、0で初期化されたndarrayを生成する関数やな。abcdで4つ生成してるねんな。

for i in r(w):
    a[:,i]=-~a[:,i-1]*(s[:,i]>'#')
    b[:,~i]=-~b[:,-i]*(s[:,~i]>'#')

Traceback (most recent call last):
  File "./Main.py", line 8, in <module>
    a[:,i]=-~a[:,i-1]*(s[:,i]>'#')
IndexError: too many indices

🐍 ACしてるのにエラーでるな。このコードの読コードはここまでや。

参考にしたコード

import numpy as np
H,W=map(int,input().split())
S=[list(input()) for h in range(H)]
S=[[1 if s=='.' else 0 for s in S[h]] for h in range(H)]
S=np.array(S)
L=S.copy()
R=S.copy()
U=S.copy()
D=S.copy()
for w in range(1,W):
    L[:,w]=(L[:,w-1]+1)*S[:,w]
    R[:,-(1+w)]=(R[:,-w]+1)*S[:,-(1+w)]
for h in range(1,H):
    U[h,:]=(U[h-1,:]+1)*S[h,:]
    D[-(1+h),:]=(D[-h,:]+1)*S[-(1+h),:]
print(int((L+R+U+D).max())-3)

S=[[1 if s=='.' else 0 for s in S[h]] for h in range(H)]

[[0, 1, 1, 0, 1, 1], [1, 1, 1, 1, 1, 0], [1, 1, 1, 1, 0, 1], [0, 1, 0, 1, 1, 1]]

🐍 ここは文字列を0と1に置き換えてるんやな。

L[:,w]=(L[:,w-1]+1)*S[:,w]

🐍 ,ってなんや外したろ

Traceback (most recent call last):
  File "./Main.py", line 12, in <module>
    L[:w]=(L[:w-1]+1)*S[:w]
ValueError: could not broadcast input array from shape (0,6) into shape (1,6)

🐍多次元の場合は、カンマ（,）で区切ってそれぞれを指定せなあかんねんな。