🐈

AtCoder ABC189 個人的メモ

2021/01/24に公開

所感

ab2完
思ったよりも冷えなかったのは良かった
勘違いしたり計算量の見積もりが甘かったりしたのは良くなかった
abc189

A - Slot

c = input()

if c[0] == c[1] == c[2]:
    print("Won")
else:
    print("Lost")

B - Alcoholic

浮動小数点なので誤差を考慮して両辺100倍
float型については↓の過去の記事に少し書いた
https://zenn.dev/m193h/articles/20201128sat230850m193harc109#b---log
自分の記事ではないがこの記事とかも詳しい
https://qiita.com/mod_poppo/items/910b5fb9303baf864bf7

N, X = map(int, input().split())

X *= 100
ans = -1
for i in range(N):
    v, x = map(int, input().split())
    X -= v * x
    if X < 0:
        ans = i + 1
        break

print(ans)

C - Mandarin Orange

l,rを全探索するとO(N^2)かかるのでこの方法は無理
と思ってたらそれが想定解だったらしい
手元で最大ケースの入力作って試してみるべきだった

別の方法を考えたけどさっぱり

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

ans = 0
for i in range(N):
    orange = A[i]
    for j in range(i, N):
        orange = min(orange, A[j])
        ans = max(ans, orange * (j - i + 1))

print(ans)

D - Logical Expression

問題文読み間違えた

y_n=Trueとなるには,x_0=True,または少なくとも1つ以上の\lorTrueが必要
最後の\lorTrueがi番目にあるとする
0\leqq j< ii<k\leqq Nとすると,以下の2つが言える

  • x_jは何でも良い
  • \land x_kx_kは全てTrue,\lor x_kx_kは全てFalse

何でも良いなら全通りを考えれば良いから,全ての\lorにおいてそれ以前の全通りの数を足してけば良い

N = int(input())
S = [input() for _ in range(N)]

ans = 1
for i in range(N):
    if S[i] == "OR":
        ans += pow(2, i + 1)

print(ans)

Discussion