ABC468のPython解答（A～E）

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

A問題

全部調べる

A

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

ans = 0
for a_0, a_1, a_2 in zip(a, a[1:], a[2:]):
    if a_0 < a_1 > a_2:
        ans += 1

print(ans)

B問題

各地点から左右の$G$までの距離を調べる

B

def check(ind, is_left):
    res = 0
    while 0 <= ind < m:
        if s[ind] == "G":
            return res
        else:
            if is_left:
                ind -= 1
            else:
                ind += 1
            res += 1

    return float("inf")


m, d = map(int, input().split())
s = input()

ans = 0
for i in range(m):
    diff = min(check(i, True), check(i, False))
    if diff > d:
        ans += 1

print(ans)

C問題

順列を全通り調べる
$10!= 3628800 $なのでプラスで辞書順を調べても間に合う

C

def check(a, b):
    for a_i, b_i in zip(a, b):
        if a_i < b_i:
            return True
        if a_i > b_i:
            return False
    return False


from itertools import permutations

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

ans = 0
for p_i in permutations([i for i in range(1, n + 1)]):
    if check(p, p_i) and check(p_i, q):
        ans += 1

print(ans)

D問題

回文の探索を各文字から左右に伸ばしていく形でやる

D

s = input()

n = len(s)
ans = 0
for i in range(n):
    diff = 0
    k = 0
    while 0 <= i - k and i + k < n:
        if s[i - k] != s[i + k]:
            diff += 1

        if diff <= 1:
            ans += 1
            k += 1
        else:
            break

    diff = 0
    left = i - 1
    right = i
    while 0 <= left and right < n:
        if s[left] != s[right]:
            diff += 1

        if diff <= 1:
            ans += 1
            left -= 1
            right += 1
        else:
            break

print(ans)

E問題

$n=5$の時、各数字に対する$1,1/2,1/3,$...の関与回数は
1,1,1,1,1
1,2,2,2,1
1,2,3,2,1
1,2,2,2,1
1,1,1,1,1
のような感じになる。
よって
$(1 +1/5 +1/2+1/4 + 1/3) * (a_1 + a_5)$
$(1 +1/5 +2*(1/2+1/4 +1/3)) * (a_2 + a_4)$
$(1+1/5 + 2*(1/2+1/4) + 3*(1/3)) * a_3$
が求められれば良い

あとは累積和をいい感じに使って計算する

E

"""
1 10 100
1/1
1/2 10/2
1/3 10/3, 100/3
    10/1
    10/2  100/2
          100/1


a b c d e
a/1
a/2 b/2
a/3 b/3 c/3
a/4 b/4 c/4 d/4
a/5 b/5 c/5 d/5 e/5
    b/1
    b/2 c/2
    b/3 c/3 d/3
    b/4 c/4 d/4 e/4
        c/1
        c/2 d/2
        c/3 d/3 e/3
            d/1
            d/2 e/2
                e/1

a:1,1,1,1,1
b:1,2,2,2,1
c:1,2,3,2,1
d:1,2,2,2,1
e:1,1,1,1,1

1+ 1/2 +1/3 + 1/4 + 1/5
1+ 2/2 +2/3 + 2/4 + 1/5
1+ 2/2 +3/3 + 2/4 + 1/5

1 +1/5 +1/2+1/4 + 1/3
1 +1/5 +2*(1/2+1/4 +1/3)
1+1/5 + 2*(1/2+1/4) + 3*(1/3)
"""

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

p1 = list()
left, right = 1, n
while left <= right:
    p_i = pow(left, -1, mod)
    if left != right:
        p_i += pow(right, -1, mod)
    p1.append(p_i)
    left += 1
    right -= 1

p_up = [0] * len(p1)
for i in range(1, len(p1) + 1):
    p_up[-i] += p1[-i]
    if i > 1:
        p_up[-i] += p_up[-i + 1]
        p_up[-i] %= mod

ans = 0
last = 0
for i in range(len(p1)):
    p = (last + p_up[i] * (i + 1) % mod) % mod
    last += p1[i] * (i + 1) % mod
    last %= mod

    target = a[i]
    if n - i - 1 != i:
        target += a[n - i - 1]
    ans += target * p % mod
    ans %= mod

print(ans)