🍣

# AtCoder ABC211 個人的メモ

2021/07/25に公開

## 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

ある文字S_iが"h"の時、0~iの範囲で部分文字列が"ch"となる個数はその範囲にある"c"の個数になる。

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

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)