AtCoder ABC129

概要

AtCoderの記録です。全部Pythonで頑張ります。
E,Fは解いてないです。

この記事の対象

• AtCoderについてある程度知っている人
• Pythonがある程度読める人

本編

AtCoderとは

競技プログラミングコンテストを開催している会社です。 atcoder.jp

ABC129

前回は大火傷したので今回挽回するぞ！と臨んだ回でした。
結果から言うとDは解法こそ早めに思いつきましたがコーディング能力が低くて時間内に提出が間に合いませんでした。

A Airplane

はい。

p,q,r = map(int,input().split())
print(min(p+q,q+r,r+p))

B Balance

シンプルに全探索。

N = int(input())
w = list(map(int,input().split()))

ans = 10**5
for i in range(N):
    diff = abs(sum(w[:i]) - sum(w[i:]))
    if diff < ans:
        ans = diff

print(ans)

C Typical Stairs

段差の高い方から低い方へ移動することはないので、低い方の階段から１つずつ順番に、そこに到達するまでの場合の数を数え上げていけば良いです。
ただし危険な階段は飛ばします。コーディング的にはわざわざ小さい順に危険な階段が与えられているので、危険な段数リストを作っておいて飛ばされたらリストの次の要素を以降の危険な段数の判定に使う…というようにしています。(a[index] == iのif文の中に入ると、index += 1となっているのがそれです。)
また、if M == 0:の部分は危険な階段がなかった場合に起こるIndexErrorの対策として書いた処理です。

N,M = map(int,input().split())
a = []
for i in range(M):
    a.append(int(input()))

if M == 0:
    a = [-1]

inf = 1000000007
index = 0
n_way = [0 for i in range(N+2)]
n_way[0] = 1

for i in range(N):
    if a[index] == i:
        index += 1
        index = min(index,len(a)-1)
    else:
        n_way[i+1] += n_way[i]
        n_way[i+1] = n_way[i+1]%inf
        n_way[i+2] += n_way[i]
        n_way[i+2] = n_way[i+2]%inf

print(n_way[N])

D Lamp

はじめランプを置く場所が複数なのかな？と思っていたら一個だけだったのでそこまで難しくなさそうに思いました。
まず、最大2000×2000のグリッドの全探索だと10⁶のオーダーで、全探索中にあれこれ計算している暇はなさそうだ、ということで事前に計算しておくことを考えます。
各マスについて、そこにランプを置いたとき照らすことになるマス数を、縦方向横方向それぞれについて事前計算しておけば、その２つを足して被っているマス１つ分を引いた値が答えじゃないか、と思いその方針でコードを書いていきます。
まず、例えば**#***##といった１列が与えられたときに[2,2,-100,3,3,3,-100,-100]というリストを返すような関数を作ります。(障害物があるマスで最大値を取らないよう-100のような数を入れておきます)
擬似コードを書いてみると

def cal(l):
　　vol = lと同じサイズのリスト
　　index = 0

　　while indexがリストの最後に達していない:
　　　　while l[index]が障害物でない and indexがリストの最後に達していない:
　　　　　　index += 1
　　　　　　連続する障害物でないマスのカウンタ += 1
　　　　for i in 障害物でなかったマスのindex:
　　　　　　vol[I] = 最終的なカウンタの値
　　　　カウンタリセット
　　　　
　　　　index += 1

　　return vol

という感じです。
フィールドを縦方向に切ったリストをこの関数に入れれば縦方向の事前計算もこれでできます。
この事前計算のオーダーはO(HW)で、これを縦方向横方向に行ったあと、全てのマスについてその合計値を比較しながら最大値を発見（これもO(HW))し、最後に1を引いてやれば答えが出ます。
なお毎度毎度のことですが、Python3ではTLEになってしまったのでPyPy3で通しました。

H,W = map(int,input().split())

def cal(l):
    ll = list(l)
    ll.append('#')
    vol = [-100 for j in range(len(ll))]
    i = 0
    while i <= len(ll)-1:
        cnt = 0
        while (ll[i] != '#' and i <= len(ll)-1):
            cnt += 1
            i += 1

        for j in range(i-cnt,i):
            vol[j] = cnt

        i += 1
    return vol[:-1]

ver = [] # 縦
hori = [] # 横
fmap = []

for h in range(H):
    l = list(input())
    hori.append(cal(l))
    fmap.append(l)



new_map = []
for i in range(len(fmap[0])):
    mini_l = []
    for j in range(len(fmap)):
        mini_l.append(fmap[j][i])
    new_map.append(mini_l)

fmap = new_map

for w in range(W):
    ver.append(cal(fmap[w]))

ans = 0

for h in range(H):
    for w in range(W):
        s = hori[h][w]+ver[w][h]
        if s > ans:
            ans = s
print(ans-1)

まとめ

無事茶色コーダーに復帰しました。
C問題のREに気づかないままDを考えていて結局Cを通したのが開始40分後とかだったのにある程度のパフォーマンスになったので、Dまで解けていたら…と思うと悔しいですね。
また次回。