ABC-375

A

$URL\:\to$ https://atcoder.jp/contests/abc375/tasks/abc375_a

#愚直

N = int(input())
S = input()

ans = 0

for i in range(N-2):
    if S[i]==S[i+2]=="#" and S[i+1]==".": ans += 1
print(ans)

解法

$i(0 \to N-3)$ で $S[i]=S[i+2]=\#\;\; \& \;\;S[i+1]=.$ となるときに $++$ すれば題意を満たせる。

B

$URL\:\to$ https://atcoder.jp/contests/abc375/tasks/abc375_b

#愚直

def distance(a,b): return ((b[0]-a[0])**2+(b[1]-a[1])**2)**0.5

N = int(input())

cp = (0,0)

ans = 0

for i in range(N):
    X,Y = map(int,input().split())
    ans += distance(cp, (X,Y))
    cp = (X,Y)
ans += distance((0,0), cp)

print(ans)

解法

処置位置を $(0,0)$ にもっておき、距離を加算し $\to$ 位置を更新を繰り返し、最後に $(0,0)$ に帰ってくると題意を満たせる。

C

$URL\:\to$

解法

D

$URL\:\to$ https://atcoder.jp/contests/abc375/tasks/abc375_b

#累積和 #文字列操作

S = Word().content
N = len(S)
grid = [[0]*(N+1) for i in range(26)]

for i in range(N):
  for j in range(26):
    grid[j][i+1] = grid[j][i] + (1 if j==(ord(S[i])-NA) else 0)

ans = 0
for i in range(1+1, N):
  for j in range(26):
    l = grid[j][i-1]
    r = grid[j][N]-grid[j][i]
    ans += l*r

print(ans)

解法

前提としてアルファベットは26文字であり、今回は $\sigma(=26)$ と置く。事前準備として、 $A \to Z$ それぞれのテーブルを持って置き、 $i(0 \to len(S))$ で回し、 $i$ 文字目のときに $A \to Z$ が何文字出現しているのかを持って置く。そして、解くフェーズに移るが、 $S_{j}(1 \le j \le len(S)-1)$ に注目したとき、 $S_{i}=S_{k}$ となるときに $++$ すると題意を満たせる。各文字に対して累積和の要領で各文字に対して、 $i$ には $[j-1]$ の数を、 $k$ には $[N]-[j]$ が入る。したがって $Ο(\sigma N)$ で解くことができ、十分に高速である。

E

$URL\:\to$