AtCoder ABC211 個人的メモ

A - Blood Pressure

A, B = map(int, input().split())

print((A - B) / 3 + B)

B - Cycle Hit

S = [input() for _ in range(4)]

if "H" in S and "2B" in S and "3B" in S and "HR" in S:
    print("Yes")
else:
    print("No")

C - chokudai

https://atcoder.jp/contests/typical90/tasks/typical90_h

文字列を左端から見ていく。
ある文字$S_i$が"h"の時、0~iの範囲で部分文字列が"ch"となる個数はその範囲にある"c"の個数になる。
同様に$S_i$が"o"の時に部分文字列が"cho"となるには"ch"の個数が分かれば良い。

S = input()
MOD = 10 ** 9 + 7
chokudai = "chokudai"

cnt = [0] * (len(chokudai) + 1)
cnt[0] = 1
for s in S:
    for i, c in enumerate(chokudai):
        if s == c:
            cnt[i + 1] += cnt[i]
            cnt[i + 1] %= MOD

print(cnt[-1])

D - Number of Shortest paths

BFS

from collections import deque

N, M = map(int, input().split())
edge = [[] for _ in range(N)]
for _ in range(M):
    x, y = map(lambda n: int(n) - 1, input().split())
    edge[x].append(y)
    edge[y].append(x)  # 有向グラフならこの行は消す!!
MOD = 10 ** 9 + 7

cnt = [0] * N
cnt[0] = 1
min_time_to_node = [10 ** 18] * N
queue = deque([(0, 0, -1)])
while queue:
    now_node, time, last_node = queue.popleft()
    # 頂点nowに今よりも早く来たか？
    # 最短時間よりも遅いならばいらない
    if min_time_to_node[now_node] < time:
        continue
    cnt[now_node] += cnt[last_node]
    cnt[now_node] %= MOD
    # 頂点nowに最短時間と同じ時間に来た？
    # 最短時間と同じならば、既にそこからの遷移は操作済みなのでここで終わり
    if min_time_to_node[now_node] == time:
        continue
    min_time_to_node[now_node] = time
    for n_node in edge[now_node]:
        if cnt[n_node]:
            continue
        queue.append((n_node, time + 1, now_node))

print(cnt[-1])

E - Red Polyomino

DFS
seen配列の座標は下図のような感じ

def rec(painted_cnt: int):
    now = sum(val * 100 ** i for i, val in enumerate(sorted(grid)))

    if now in seen:
        return 0
    seen.add(now)

    if painted_cnt == K:
        return 1

    res = 0
    # 現在の赤マスそれぞれから隣接マスへ赤マスを増やせるかを試す
    for red in grid:
        i = red // N
        j = red % N
        for di, dj in [(1, 0), (-1, 0), (0, 1), (0, -1)]:
            n_i = i + di
            n_j = j + dj
            n_red = n_i * N + n_j
            if 0 <= n_i < N and 0 <= n_j < N and S[n_i][n_j] == "." and n_red not in grid:
                grid.append(n_red)
                res += rec(painted_cnt + 1)
                grid.pop()

    return res


N = int(input())
K = int(input())
S = [input() for _ in range(N)]

seen = set()
ans = 0
for i in range(N):
    for j in range(N):
        if S[i][j] == "#":
            continue
        grid = [i * N + j]
        ans += rec(1)

print(ans)