ABC189
何も精進しないで週に一回コンテストに出るだけでは成長するわけがないと思うので、今回以降は時間が余ったら、解説を先に書くのではなく、青の問題を1問解くことにしよう。ABCの問題数を勝手に7問にするアプローチ。 ABC110D https://gyazo.com/d234f81a5294e5b0a658e36ec971f2f3
EのTLEが解決しなくて4問しか解けなかった。水色に落ちるかと思ったが踏みとどまった。
https://gyazo.com/16f946ef228f369f1a0dbf3f3c007f89
https://gyazo.com/eb68cd541517250df77564e56374120f
浮動小数点数の大小比較、誤差でハマるのが嫌なので100倍して整数にした
code:python
def main():
N, X = map(int, input().split())
X *= 100
total = 0
for i in range(N):
V, P = map(int, input().split())
total += V * P
if total > X:
print(i + 1)
return
print(-1)
https://gyazo.com/2f0680970cbdbd53b9343c2020e5d1fa
10^8が間に合うかどうか不安で、値の小さい方から順に領域を分割していくか？と考えたが、難しく考えすぎな気がしたので一旦保留して先にDを解いた
戻ってきてから改めて考えると、10^8でも中身を軽くできそうだから試してみよう
646ms AC
code:python
def main():
N = int(input())
AS = list(map(int, input().split()))
ret = max(AS)
for i in range(N):
width = 1
for j in range(i + 1, N):
width += 1
v = maxA * width
if v > ret:
ret = v
print(ret)
https://gyazo.com/fd1d24b429cec954a5df9d2257d212a9
1つ項を増やした時にどう変化するか考える
ANDの時には「増やす項もTrueでなければならない」から場合の数が増えない
ORの時は「増やす項がTrueの時、過去の状況に関係なくTrue」なので2^iくらい増える
https://gyazo.com/f76f3dc694e4fcbd5f14cbcea8e9a8ba
code:python
def main():
N = int(input())
prev = 1
for i in range(N):
S = input().strip().decode('ascii')
if S == "OR":
prev = prev + (2 ** (i + 1))
print(prev)
https://gyazo.com/9bb7f06e46fed0c174035ca151c9a7a4
最初(1, 0)と(0, 1)の変化だけ追ってた
サンプルが合わなくて「おっと、原点がズレる変換があるから斉次行列にしなきゃダメか」 Numpyを使う路線に方針転換
TLEが取れなくて時間を食いつぶしてしまった。
code:python
def main():
N = int(input())
XY = []
for _i in range(N):
XY.append(tuple(map(int, input().split())))
M = int(input())
timeline = []
for i in range(M):
timeline.append(((i + 1) * 2, tuple(map(int, input().split()))))
Q = int(input())
QS = []
for i in range(Q):
q = tuple(map(int, input().split()))
QS.append(q)
timeline.append((q0 * 2 + 1, q)) timeline.sort()
answer = {}
trans = np.eye(3, dtype=np.int64)
OP1 = np.array([
OP2 = np.array([
OP3 = np.array([
OP4 = np.array([
for t, x in timeline:
if t % 2:
# query
q = x
newXY = np.array(x, y, 1).dot(trans) answerq = (newXY0, newXY1) else:
# ops
trans = trans.dot(OP1)
trans = trans.dot(OP2)
trans = trans.dot(OP3)
trans = trans.dot(OP4)
for q in QS:
print(int(x), int(y))
Twitter
E問題は、(0,0),(1,0),(0,1)の3点だけシミュレーションすれば全部計算できる/この解法ならCで200ms、pypyで1400msだけど、アフィン変換の変換行列の累積積を使う解法だとpypyでも2100msくらいでTLEになるみたいだねー。src まさにそれ
小さな行列の掛け算を繰り返す場合、Numpyを使ってもオーバーヘッドが大きくてメリット少ないのだな
code:python
def dot(a, b):
return [
]
「絶対コンテスト中書いてたらインデックスミスってバグって無気力になる自信ある。」src もちろんプログラムに書かせた()
code:python
def gen_dot():
for i in range(9):
x, y = divmod(i, 3)
print(
https://gyazo.com/c98e3a76d7f6ec84fb0970d0d5686351
公式解説の一次式DPに相当する解法
Eで時間を使って残り20分でギリギリ実装したのでバグが取れずnoSub
基本はこう
$ f(i) = 1 + \frac{1}{M} \sum_{j=1}^Mf(i+j)
例外: i in ASの時
$ f(i) = f(0)
$ x = f(0)とするとf(i)はax + bの形になる、なのでこの係数をDPする
最終的に $ f(0) = ax + b が得られたら:
$ f(0) = a f(0) + b
$ (1 - a)f(0) = b
$ f(0) = b / (1 - a)
本番では最初から累積和高速化をやろうとしてバグらせたのでまずは素朴に書く。下記でサンプルAC
code:python
def solve(N, M, K, AS):
setA = set(AS)
for i in range(N - 1, -1, -1):
if i in setA:
else:
v = 0
f = 0
for j in range(1, M + 1):
return -1
return table0 / (1 - tableF0) 累積和に書き換えて提出、3WA
code:python
def solve(N, M, K, AS):
setA = set(AS)
sumTable = 0
sumTableF = 0
for i in range(N - 1, -1, -1):
if i in setA:
else:
v = sumTable
f = sumTableF
sumTable += tablei - tablei + M sumTableF += tableFi - tableFi + M return -1
return table0 / (1 - tableF0) これは到達不能のチェックに取りこぼしがあるせいなので真面目にチェックしてAC