AtCoder Beginner Contest 182 (A,B,C,D,E) 感想

ABC182の感想です。先に解きたい人は解いてから見てねー。（定型文）

A問題(twiblr)
B問題(Almost GCD)
C問題(To 3)
D問題(Wandering)
E問題(Akari)
感想
- Reference

A問題(twiblr)

f:id:physics-heibon:20201110014252p:plain
言われた通りやります。

a, b = map(int, input().split())
print(-b +2*a + 100)

B問題(Almost GCD)

f:id:physics-heibon:20201110014449p:plain
各 $A_i$ の正の約数を列挙して、出てきた数の個数が一番大きいものを出力すればいいです。出力する時は1は考えないことに注意です。

def make_divisors(n):
    lower_divisors , upper_divisors = [], []
    i = 1
    while i*i <= n:
        if n % i == 0:
            lower_divisors.append(i)
            if i != n // i:
                upper_divisors.append(n//i)
        i += 1
    return lower_divisors + upper_divisors[::-1]




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

T = [0]*1002
for i in range(N):
    L = make_divisors(A[i])
    for j in range(len(L)):
        T[L[j]] += 1

#print(T[:10])
T.pop(0)
T.pop(0)
#print(T[:10])
ans = T.index(max(T))
print(ans + 2)

C問題(To 3)

f:id:physics-heibon:20201110022829p:plain
まず「桁」って単語と制約を見てbit全探索かなって思いました。例えば4桁の整数が与えられた時、4桁目と2桁目を取ってきたかったら $\{1010\}$ という集合で表したりできます。これを全通り試すと、制約的に $2^{18}=O(10^5)$ なので計算量的に大丈夫です。
Twitterを見てると、「抜き取る数は高々2個だから全探索(二重ループ)でできる」と書いていて、確かに〜！って感じです。mod　3で考えると、入力がそのままで（どの桁も抜き取らないで）3の倍数でないなら1 or 2 (mod 3) ですから、3の倍数以外を抜いていくといいんですね。頭いい〜。

import sys
N = input()
k = len(N)

ans = 10**9
update = False
for i in range(2**k):
    res = []
    for j in range(k):
        #print(j>>k)
        if (i>>j) &1:
            res.append(N[j])
    #print(res)
    l = len(res)
    if l==0:
        if int(N)%3 == 0:
            print(0)
            sys.exit()
        else:
            continue  
    res = "".join(res)
    #print(res)
    res = int(res)
    if res %3==0:
        ans = min(ans,k-l)
        update = True
if update: print(ans) 
else:print(-1)

D問題(Wandering)

f:id:physics-heibon:20201110015734p:plain

WAだしまくりんぐです！Aの累積和をとれば「i回目に進んだ距離」が出て、その累積和を取ればロボットがi回目終了時にどこにいるかが分かります。求める最大値は、i回目終了時の最大値の前後の操作の中で達成されるはず（ほんまに？）ですから、その辺りを調べればO(N)で解けました。

解説は上の考えをもっとスマートにした感じですね。Aの累積和(cum_Aとする)をとって「i回目の操作でどれだけ進めるか」という情報を持っておいて、さらに「i回目の操作の中で進める最大値」という情報も先に持っておきます。（tmp = 0 として、tmp = max(cum_A[i],tmp)と更新していくとできます。）

コンテスト中

import sys
N = int(input())
A = list(map(int, input().split()))
s = []
tmp = 0
for i in range(N):
    tmp += A[i]
    s.append(tmp)
t = []
tmp = 0
for i in range(N):
    tmp += s[i]
    t.append(tmp)
# print(s)
# print(t)
g1 = max(t)
ans = max(g1,0)

g1 = max(t)
#print(t)
for i in range(t.index(g1),-1,-1):
    g1 -= A[i]
    ans = max(ans,g1)
g1 = max(t)
if t.index(g1) == N -1 :
    print(ans)
    sys.exit()
else:
    for i in range(t.index(g1)+1):
        g1 = g1 + A[i]
        ans = max(ans,g1)
print(ans)

解答を見た後

import sys
N = int(input())
A = list(map(int, input().split()))
p = []#動作iの合計の座標の変化
tmp = 0
for i in range(N):
    tmp += A[i]
    p.append(tmp)
q = [] #動作iを座標0ではじめた場合の、開始から終了までの座標の最大値

tmp = 0
for i in range(N):
    tmp = max(tmp,p[i])
    q.append(tmp)

# print(p)
#print(q)
ans = 0
tmp = 0
for i in range(N):
    ans = max(ans,tmp+q[i])
    tmp += p[i]

print(ans)

E問題(Akari)

f:id:physics-heibon:20201110021805p:plain

またもやE問題解けませんでした‥。
D - LampABC129のLampみがあるなぁと思ったんですが、Dで時間かけすぎてて実装できませんでした。
コンテスト後、ほとんど愚直にやりました。ランプを起点にビームを出して、壁かランプに当たるまで伸ばすのを四方向繰り返します。制約的に厳しかったので、入力をreadlineにしたりPyPy3で提出したりと工夫してます。

import os

from sys import stdin
readline = stdin.readline
H,W,N,M = map(int,readline().split())

q = []

bright = [[False]*W for _ in range(H)]
light = [[False]*W for _ in range(H)]
wall = [[False]*W for _ in range(H)]
for i in range(N):
    a,b = map(lambda x: int(x)-1,readline().split())
    light[a][b] = True
    q.append([a,b])

for i in range(M):
    a, b = map(lambda x: int(x)-1,readline().split())
    wall[a][b] = True


d = [[-1,0],[1,0],[0,1],[0,-1]]
ans = 0
for a,b in q:
    if bright[a][b] == False:
        ans += 1
    bright[a][b] = True

    for i in range(4):
        dy = d[i][0]
        dx = d[i][1]
        ny = a + dy
        nx = b + dx
        while 0<=nx<W and 0<=ny<H:
            if wall[ny][nx] or light[ny][nx]:
                break
            if bright[ny][nx] == False:
                ans += 1
            bright[ny][nx] = True
            nx += dx
            ny += dy
    for i in range(H):
        print(bright[i])
    #print("______")


print(ans)