Pythonで毎日AtCoder #46

はじめに

前回

#46

ABC131-D

考えたこと
$B_i$でsortして仕事を終らせるのに必要な時間を計算していきます。制限時間を越えたらflagを変えます。

n = int(input())
ab = [list(map(int,input().split())) for _ in range(n)]

ab.sort(key=lambda x: x[1])
t = 0
flag = True
for i in range(n):
    t += ab[i][0]
    if t > ab[i][1]:
        flag = False
if flag:
    print('Yes')
else:
    print('No')

ARC093-C

考えたこと
Nの大きさ的に$O(N^2)$は通せません。なので、うまく$O(N)$くらいにします。スタートとゴールの座標は0なので、左右に0を追加します。dを$|a[i+1]-a[i]|、0\leq i \leq N$、dの総和$sum(d)$をsとします。すると、観光スポット$i$をスキップしたときは、$s+|a[i+1]-a[i-1]|-(|a[i]-a[i-1]|+|a[i+1]-a[i]|$となります。

n = int(input())
a = list(map(int,input().split()))

a.insert(0,0)
a.append(0)
d = [abs(a[i]-a[i+1]) for i in range(n+1)]
s = sum(d)
for i in range(1,n+1):
    print(s+abs(a[i-1]-a[i+1])-(abs(a[i-1]-a[i])+abs(a[i]-a[i+1])))

まとめ

2問目は少し考えてしまった。Nが大きいから計算量を減らさないといけないのは気付いたけど、減らし方がうまくできなかった。ではまた、おやすみなさい。