競ぷろぐ

アルゴリズムのまとめ(Python/C++)と気が向いたときに社会学もまとめる

数学パズル | Q11 オリンピックの開催都市投票

N = 3

def vote(n):
    if (n <= 2): return 1
    # 1つが過半数で決定
    cnt = 1
    # 1つが脱落して、それを除いてやり直し
    cnt += vote(n-1)
    # 下位i個が並ぶ
    for i in range(2, n):
        # 下位i個から1つ選ぶ、それを除いてやり直し
        cnt += vote(i) * vote(n-1)

    return cnt

print(vote(N))

数学パズル | Q05 枚数で考えるパスカルの三角形

n = 7
row = [0] * n
row[0] = 1

for i in range(n):
    for j in range(i, 0, -1):
        row[j] += row[j-1]

print(row) # [1, 6, 15, 20, 15, 6, 1]
def p(n, k):
    if(k <= 0 or n <= k):
        return 1
    else:
        return(p(n-1, k-1) + p(n-1, k))


n = 6

print([p(n, k) for k in range(n+1)]) # [1, 6, 15, 20, 15, 6, 1]

数学パズル | Q03 ローマ数字の変換規則

import math

n = 12

# 1桁分の変換
def conv(n, i, v, x):
    result = ""
    if (n == 9):
        result += i + x
    elif (n == 4):
        result += i + v
    else:
        for _ in range(math.floor(n/5)):
            result += v
        n = n % 5
        for _ in range(n):
            result += i
    
    return result

# ローマ数字への変換
          # 3894 = 3000 + 800 + 90 + 4
def roman(n):
    # 3
    m = math.floor(n / 1000)
    # 894
    n %= 1000
    # 8
    c = math.floor(n / 100)
    # 94
    n %= 100
    # 9
    x = math.floor(n / 10)
    # 4
    n %= 10
    # MMM
    result = 'M' * m
    result += conv(c, 'C', 'D', 'M')
    result += conv(x, 'X', 'L', 'C')
    result += conv(n, 'I', 'V', 'X')

    return result

cnt = {}
for i in range(1, 4000):
    length = len(roman(i))
    if (length in cnt):
        cnt[length] += 1
    else:
        cnt[length] = 1
    
print(cnt[n])

atcoder過去問 | AGC157 A - Darker and Darker

atcoder.jp

from collections import deque

H, W = map(int, input().split())
grid = [input() for i in range(H)]

# 初期の黒('#')の位置からの距離
dist = [[-1]*W for _ in range(H)]

# '#'の位置をキューに追加(=今回はこれが複数あるので、複数スタートとなる)
black_cells = deque()
for h in range(H):
    for w in range(W):
        if grid[h][w] == '#':
            black_cells.append((h, w))
            dist[h][w] = 0

def bfs(black_cells, dist):
    d = 0
    while black_cells:
        # キューとして使うのでpop()ではなくpopleft()
        h, w = black_cells.popleft()
        # 足された距離が返される
        d = dist[h][w]
        for dy, dx in ((1, 0), (0, 1), (-1, 0), (0, -1)):
            new_h = h + dy
            new_w = w + dx
            if new_h < 0 or H <= new_h or new_w < 0 or W <= new_w:
                continue
            if dist[new_h][new_w] == -1:  # セルが白('.')であるのと同義
               # 距離が足されてく
               dist[new_h][new_w] = d + 1
               black_cells.append((new_h, new_w))
    return d

d = bfs(black_cells, dist)
print(d)

qiita.com

atcoder過去問 | ABC088 D - Grid Repainting

atcoder.jp

from collections import deque

INF = 10**5
H, W = map(int,input().split())
S = [input() for _ in range(H)]
cntSharp = 0
for i in range(H):
   cntSharp += S[i].count("#")

dp = [[INF]*W for _ in range(H)]
dp[0][0] = 0

dx = [1,0,-1,0]
dy = [0,1,0,-1]
P = deque([])
P.append((0,0))
while P:
   p = P.popleft()
   x,y = p[0], p[1]
   for i in range(4):
       nx,ny = x + dx[i], y + dy[i]
       if 0 <= nx and 0 <= ny and nx <= H-1 and ny <= W-1 and S[nx][ny] =="." and dp[nx][ny] == INF:
           dp[nx][ny] = dp[x][y] + 1
           P.append((nx,ny))
if dp[H-1][W-1] == INF:
   print(-1)
else:
   print(H*W - dp[H-1][W-1] - cntSharp - 1)

atcoder過去問 | 第10回日本情報オリンピック 予選 E - チーズ (Cheese)

atcoder.jp

from collections import deque

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

def bfs(q, d, maps, h , w):
    # 地点x, 地点y
    s_x, s_y = q[0][1], q[0][0]

    while len(q) != 0:
        # 地点
        now = q.popleft()
        for i, j in [[-1, 0], [0, 1], [0, -1], [1 ,0]]:
            # 行き先
            go = [now[0] + i, now[1] + j]
            # 行けない
            if go[0] < 0 or go[0] >= h or go[1] < 0 or go[1] >= w:
                continue
            # 行けない
            if maps[go[0]][go[1]] == 'X':
                continue
            # 行けない
            if go[0] == s_y and go[1] == s_x:
                continue
            # 行ったことがない
            if d[go[0]][go[1]] == 0:
                # 距離 += 1
                d[go[0]][go[1]] = d[now[0]][now[1]] + 1
                q.append([go[0], go[1]])
    return d

# スタート地点を0, チーズ工場を1以降に
cheeses = [None] * (n + 1)
for i in range(h):
    for j in range(w):
        if maps[i][j] != '.' and maps[i][j] != 'X' and maps[i][j] != 'S':
            cheeses[int(maps[i][j])] = [i, j]
        if maps[i][j] == 'S':
            cheeses[0] = [i, j]

# .X..1
# ....X
# .XX.S
# .2.X.
# print(cheeses) # [[2, 4], [0, 4], [3, 1]]

ans = 0
for i in range(n):
    # 地点
    q = deque([cheeses[i]])
    # 二点間の距離
    d = [[0] * w for _ in range(h)]
    # 二点間の距離足していく
    ans += bfs(q, d, maps, h, w)[cheeses[i + 1][0]][cheeses[i + 1][1]]

print(ans)

taxfree-python.hatenablog.com