ABC181 C - Collinearity を解いた。おまけ B 問題付き

100C3 : 全探索しても ザックリ O(300000)。
間に合う。

abc181c.py

N = int(input())
lis = []
for _ in range(N):
    x,y = map(int,input().split())
    lis.append([x,y])

from itertools import combinations
for a,b,c in combinations(range(N),3):
    if (lis[a][0]-lis[b][0])*(lis[a][1]-lis[c][1]) == (lis[a][0]-lis[c][0])*(lis[a][1]-lis[b][1]):
        print("Yes")
        exit()
print("No")

サクッと書いて TLE。理由もコメントで入れました。

abc181b_ng.py

N = int(input())
memo = []

for _ in range(N):#O(10^5)
    a,b = map(int,input().split())
    memo.extend(range(a,b+1))#worst O(10^6)
print(sum(memo))
##maximum O(10^11) => TLE

対策はこれ。

abc181b_ok.py

N = int(input())
memo = []

def cal(n):#n が偶数、奇数の何れでも必ず 2 で割り切れる
    return (n*(1+n))//2

for _ in range(N):
    a,b = map(int,input().split())
    memo.append(cal(b)-cal(a-1))
print(sum(memo))