ABC418をPythonで（A～E）

AtCoder Beginner Contest 418の解答等の速報的まとめ

A問題

後ろ3文字がteaか比較する

A

n = int(input())
s = input()
print("Yes" if s[-3:] == "tea" else "No")

B問題

全パターン調べる

B

s = input()
ans = 0
for i in range(len(s)):
    for j in range(i, len(s)):
        if j - i - 1 > 0 and s[i] == s[j] == "t":
            ans = max(ans, (s[i + 1:j].count("t")) / (j - i - 1))

print(ans)

C問題

答え-1で勝てないパターンはそれぞれ$min(b-1, a_i)$個選択されたパターンなので
$a_i<b$となるものは累積和で計算し、それ以降は$(b-1) \times (b$以上の個数$)$で求め、それに+1すれば最小値になる

C

from bisect import bisect_left

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

accu = [0]
for a_i in a:
    accu.append(accu[-1] + a_i)

for _ in range(q):
    b = int(input())
    if a[-1] < b:
        print(-1)
    elif b == 1:
        print(1)
    else:
        ind = bisect_left(a, b)
        print(accu[ind] + (b - 1) * (n - ind) + 1)

D問題

操作はどこから行っても結果は同じだから前から順に操作する
$dp[i][j] = t_iまでの部分列で操作をした時の結果が[0のパターン数, 1のパターン数]$
道中で答えに加算していけば直前の結果しかいらないからzero,oneの２変数だけでdpの処理を行った

D

n = int(input())
t = input()

ans = 0
zero, one = 0, 0

for t_i in t:
    if t_i == '0':
        ans += zero
        zero, one = one + 1, zero
    elif t_i == '1':
        ans += one + 1
        zero, one = zero, one + 1

print(ans)

E問題

平行な辺の組を求めればほぼ答えになる
例外は平行四辺形になるときであり、平行四辺形の個数分無駄に加算する。
「同じ傾きで線分の長さが一致するペア」÷２個平行四辺形ができるので最後の答えから引けばいい

E

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

ans = 0
d = dict()
para = 0
for i in range(n):
    x_i, y_i = points[i]
    for j in range(i+1, n):
        x_j, y_j = points[j]
        if x_i == x_j:
            diff = "inf"
        else:
            diff = (y_i - y_j) / (x_i - x_j)
        length = (x_i - x_j) ** 2 + (y_i - y_j) ** 2

        if diff in d:
            ans += d[diff]["count"]
            if length in d[diff]:
                para += d[diff][length]
            else:
                d[diff][length] = 0
            d[diff]["count"] += 1
            d[diff][length] += 1
        else:
            d[diff] = {"count": 1, length: 1}

print(ans - para // 2)