ABC351をPythonで（A～D、F）

AtCoder Beginner Contest 351の解答等のまとめ

A問題

先攻がとった点数から後攻がとった点数を引くと後攻が引き分けになるための点数になる。
よってそれに1を足せばいい。

A

print(sum(map(int, input().split())) - sum(map(int, input().split())) + 1)

B問題

全て調べて違う座標を表示すればいい

B

n = int(input())
a = [input() for _ in range(n)]
b = [input() for _ in range(n)]

for i in range(n):
    for j in range(n):
        if a[i][j] != b[i][j]:
            print(i + 1, j + 1)

C問題

数の変化の仕方に気を付けて愚直にやる

C

n = int(input())

s = list()
for a_i in map(int, input().split()):
    now = a_i
    while s and s[-1] == now:
        now += 1
        s.pop()
    s.append(now)

print(len(s))

D問題

根本はBFS
磁石の周辺でない場所から移動できる場所をBFSで調べる
ただ、磁石の周辺に移動するときのフラグの持ち方に気を付ける

D

from collections import deque

h, w = map(int, input().split())
field = [input() for _ in range(h)]

ans = 1
check = [[False] * w for _ in range(h)]
for i in range(h):
    for j in range(w):
        if field[i][j] == "#" or check[i][j] or any(
                field[a][b] == "#" for a, b in [(i + 1, j), (i - 1, j), (i, j + 1), (i, j - 1)] if
                0 <= a < h and 0 <= b < w):
            continue
        q = deque()
        q.append([i, j])
        searched = {(i, j)}
        while q:
            x, y = q.popleft()
            mag = False
            for x_i, y_i in [(x + 1, y), (x - 1, y), (x, y + 1), (x, y - 1)]:
                if 0 <= x_i < h and 0 <= y_i < w:
                    mag |= field[x_i][y_i] == "#"
            if not mag:
                check[x][y] = True
                for x_i, y_i in [(x + 1, y), (x - 1, y), (x, y + 1), (x, y - 1)]:
                    if 0 <= x_i < h and 0 <= y_i < w:
                        if (x_i, y_i) not in searched:
                            searched.add((x_i, y_i))
                            q.append([x_i, y_i])

        ans = max(ans, len(searched))

print(ans)

F問題

数列を後ろから考える
各$a_i$で、$a_i$より先に出た数の中で

• $a_i$より大きい数が何個あるか
• $a_i$より大きい数の総和

が求まれば

• ($a_i$より大きいもの)の総和$- a_i \times (a_i$より大きいもの)の個数

の和が答えになる

F

from sortedcontainers import SortedList


class BinaryIndexTree:
    def __init__(self, n):
        self.size = n
        self.tree = [0] * (n + 1)

    def sum(self, i):
        s = 0
        while i > 0:
            s += self.tree[i]
            i -= i & -i
        return s

    def add(self, i, x):
        while i <= self.size:
            self.tree[i] += x
            i += i & -i

    def range_sum(self, i, j):
        if i == 0:
            return self.sum(j)
        return self.sum(j) - self.sum(i - 1)


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

lst = sorted(set(a))
d = {l_i: i + 1 for i, l_i in enumerate(lst)}
ans = 0
s = SortedList([])
BIT = BinaryIndexTree(n + 10)
for a_i in a[::-1]:
    i = len(s) - s.bisect_right(a_i)
    if i:
        ans += BIT.range_sum(d[a_i] + 1, n + 1) - a_i * i
    s.add(a_i)
    BIT.add(d[a_i], a_i)

print(ans)