ABC 183　さくさくまとめ

しいしい

ABC183のまとめやってくよー E解けなかったから早ときに助けられた感じかな

f:id:whitesiro1107:20201121121018p:plain

A - ReLU

ReLU関数を作ろうって問題タイトルだけで実装がわかって少しくすっと来たよね

x = int(input())
print(max(0,x))

B - Billiards

二点が与えられるのでX軸に当たってからもう片方の点に移動する場合にX軸上のどの点に当たるかという問題。幾何がきてかなりびびったよね

考察ノートは２つ考えた。本番は＜Ⅰ＞の方を実装したが＜Ⅱ＞のほうが絶対かんたんっておもう

＜Ⅰ＞

a,b,c,d = map(int,input().split())
C = c-a
D = d+b
e = d - D/C*c
A = D/C
print(-e/A)

＜Ⅱ＞

a,b,c,d = map(int,input().split())
print(a+(c-a)*b/(b+d))

C - Travel

順列型全探査だね。itertoolsまとめないとなーってお気持ち。どこからどこへ行くってのが必要なので一個前添字を保管するのを忘れない！

import itertools
n,k = map(int,input().split())
Lis = []
for i in range(n):
    tmp_list = list(map(int,input().split()))
    Lis.append(tmp_list)
patterns = list(itertools.permutations(range(1,n))) #順列生成
ans = 0
for pattern in patterns:
    before_index = 0
    tmp_sum = 0
    check_lis = [0]
    for index in pattern:
    tmp_sum += Lis[before_index][index]
    before_index = index
    check_lis.append(index)
    tmp_sum+=Lis[before_index][0] #back to start
    # print(tmp_sum,check_lis)
    if tmp_sum == k:ans+=1
print(ans)

D - Water Heater

問題分概要：区間[S,T)にPというがN個与えられます。区間の総和がWを超えることが存在するか否か判断しなさい。

最初セグ木かなおもったけどいもすで瞬殺だね。セグ木も練習足りてないからここらへんで悩むのは少しもったいないかな。

n,w = map(int,input().split())
dp = [0]*(2*10**5+10)
l = []
for i in range(n):
  s,t,p = map(int,input().split())
  l.append([s,t,p])
  dp[s]+=p
  dp[t]-=p
for i in range(len(dp)-1):
  dp[i+1] += dp[i]
M = 0
for i in dp:
  M = max(M,i)
  
if M <= w:
  print("Yes")
else:
  print("No")

E - Queen on Grid （解説AC）

問題概要：チェスのクイーンが右、下、右下飲み進める場合に盤面の左上（１，１）から右下（H,W）まで行く方法は何通りあるか。”＃”は進むことができないマスとする。

EDPCのGrid１を思い浮かべたけどうーんってかんじで結局止まってしまった。こういう問題見ると組み合わせとかするのかなって思うけどとても単純なDPで行けたりするから練習不足だね。またまとめる。

h,w=map(int,input().split())
mod=10**9+7
dp=[[0]*(w+1) for i in range(h+1)]
X=[[0]*(w+1) for i in range(h+1)]
Y=[[0]*(w+1) for i in range(h+1)]
Z=[[0]*(w+1) for i in range(h+1)]

dp[0][0]=1
l = []
MOD = 10**9+7

for i in range(h):
    t_l = input()
    l.append(t_l)
for i in range(h):
    for j in range(w):
        if i + j == 0:continue
        if l[i][j]!='#':
            if j > 0:
                X[i][j] = X[i][j-1] + dp[i][j-1]
            if i > 0:
                Y[i][j] = Y[i-1][j] + dp[i-1][j]
            if i > 0 and j > 0:
                Z[i][j] = Z[i-1][j-1] + dp[i-1][j-1]
            dp[i][j] = X[i][j] + Y[i][j] + Z[i][j]
            dp[i][j]%=MOD

print(dp[-2][-2]%mod)

感想

今のレートならNosub戦法とるより前からどんどん出したほうがレート上がるので出続けたいね。

めっちゃ久々にHighest更新できたのはすこしうれしかったな。。

ここまで読んでいただきありがとうございます

しい

ABC 183 さくさくまとめ