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

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

atcoder.jp

A問題(ReLU)

言われた通りやります。
深層学習でよく見る子（活性化関数）ですね？？

def f(x):
    if x>=0:
        return x
    else:
        return 0

x = int(input())
print(f(x))

B問題(Billiards)

塾講師あるある、中学数学の定石に詳しくなる。
これは中学二年生の数学でよくある、ゴールまたはスタートの点をx軸対称な点に移して一次関数で考えると楽です。私はゴールの点を移しました。あとはその二点を通る直線の方程式において、y=0の時のx座標を求めれば終わりです。

sx, sy, gx, gy = map(int, input().split())

gy = -gy
ans = sx - sy * (gx-sx)/(gy-sy)
print(ans)

C問題(Travel)

最初に見た時TSP(巡回セールスマン問題)！？と思って、bitDPの理解が無い自分は焦りました。すぐにD問題にいって、帰ってきてよく考えると辿る道順は 0→(1~N-1 のpermutation)→0なので、全通り試せばいいですね。N=2の時にWA出してしまいましたので、別で書いときました。

N, K = map(int, input().split())
T = []
for _ in range(N):
    tmp = list(map(int, input().split()))
    T.append(tmp)

if N == 2:
    if T[0][1] + T[1][0] == K:
        print(1)
        exit()
    else:
        print(0)
        exit()



L = [i for i in range(1,N)]
ans = 0
from itertools import permutations
for perms in permutations(L):
    # print(perms)
    res = T[0][perms[0]]
    for i in range(N-2):
        now = perms[i]
        Next = perms[i+1]
        res += T[now][Next]
    res += T[Next][0]
    # print(res)
    if res == K:
        ans += 1
print(ans)

D問題(Water Heater)

問題文を読み終わった時には imos 法だなーと思ってました。できたのでラッキーです。

N, W = map(int, input().split())
S, T, P = [0]*N, [0]*N, [0]*N
for i in range(N):
    S[i], T[i], P[i] = map(int, input().split())

imos = [0]*10**6
for i in range(N):
    imos[S[i]] += P[i]
    imos[T[i]] -= P[i]

oyu = [0]*10**6
tmp = 0
for i in range(N):
    tmp += imos[i]
    oyu[i] = tmp
    if oyu[i] >W:
        print("No")
        exit()
print("Yes")
    

E問題(Queen on Grid)

またもやE問題解けませんでした‥。（もはや定型文）
多分dpで、TLE回避のために累積和を使うんだろうなーというのは分かりましたが、具体的にどこを累積和にするのか思いつきませんでした。解説を見ると非常にシンプルに書かれていて綺麗です。
やはりちゃんと数式に落とし込んで考えるって大事ですね。以下のコードは解説を見て書いたものです。PyPyで通ります。

H, W = map(int, input().split())
S = []
for _ in range(H):
    S.append(input())

dp = [[0]*W for _ in range(H)]
dp[0][0] = 1
X = [[0]*W for _ in range(H)]
Y = [[0]*W for _ in range(H)]
Z = [[0]*W for _ in range(H)]
mod = 10**9+7

for i in range(H):
    for j in range(W):
        if 0<=j-1 and S[i][j] != "#":
            X[i][j] += X[i][j-1] + dp[i][j-1]
            X[i][j] %= mod
        if 0<=i-1 and S[i][j] != "#":
            Y[i][j] += Y[i-1][j] + dp[i-1][j]
            Y[i][j] %= mod
        if 0<=i-1 and 0<=j-1 and S[i][j] != "#":
            Z[i][j] += Z[i-1][j-1] + dp[i-1][j-1]
            Z[i][j] %= mod
        if S[i][j] != "#":
            dp[i][j] += X[i][j] + Y[i][j] + Z[i][j]
            dp[i][j] %= mod

print(dp[H-1][W-1]%mod)

感想

4完(パフォーマンス982)でレート56あがりました！うれぴよ。
先週から毎日difficulty緑問題を解いてますが、強くなった気がしないです。今まではとにかく量をこなして典型問題を知ることを目的に演習していましたが、今週は毎日1問E問題をじっくりやってみます。

よくTwitterで「年内に緑行きたい！」とか言ってますが、実はそんなに思ってないです。期限決めてやると精神的につらいので、楽しいと思えるペースで適当にやります。

Reference

AtCoder