キャディプログラミングコンテスト2021(AtCoder Beginner Contest 193) C,D,E,F問題メモ

n = int(input())

ans = n

checked = set()

for k in range(2, 10 ** 5 + 1):
    if k * k > n:
        break

    t = k * k
    while t <= n:
        if t in checked:
            break
        ans -= 1
        checked.add(t)
        t *= k

print(ans)

from collections import Counter

k = int(input())
s = input()
t = input()

count = Counter(s + t)


def score(s):
    c = Counter(s)
    res = 0
    for i in range(1, 10):
        res += i * 10 ** c[str(i)]
    return res


ans = 0
for i in range(1, 10):
    if count[str(i)] >= k:
        continue
    tak = score(s[:4] + str(i))
    p = (k - count[str(i)]) / (9 * k - 8)

    for j in range(1, 10):
        if count[str(j)] + int(i == j) >= k:
            continue
        aok = score(t[:4] + str(j))
        q = (k - count[str(j)] - int(i == j)) / (9 * k - 9)
        if tak > aok:
            ans += p * q

print(ans)

ライブラリ用意してなかったので以下のサイトを使わせていただいた。感謝。

• 【math編】AtCoder Library 解読 〜Pythonでの実装まで〜 - Qiita

def inv_gcd(a, b):
    # 略


def crt(r, m):
    # 略


t = int(input())
INF = 1 << 60
for _ in range(t):
    x, y, p, q = map(int, input().split())

    ans = INF
    for i in range(y):
        for j in range(q):
            r, m = crt([x + i, p + j], [2 * x + 2 * y, p + q])
            if r == 0 and m == 0:
                continue
            ans = min(ans, r)
    if ans == INF:
        print('infinity')
    else:
        print(ans)

from collections import deque


class Dinic:
    def __init__(self, n):
        self.n = n
        self.links = [[] for _ in range(n)]
        self.depth = None
        self.progress = None

    def add_link(self, _from, to, cap):
        self.links[_from].append([cap, to, len(self.links[to])])
        self.links[to].append([0, _from, len(self.links[_from]) - 1])

    def bfs(self, s):
        depth = [-1] * self.n
        depth[s] = 0
        q = deque([s])
        while q:
            v = q.popleft()
            for cap, to, rev in self.links[v]:
                if cap > 0 and depth[to] < 0:
                    depth[to] = depth[v] + 1
                    q.append(to)
        self.depth = depth

    def dfs(self, v, t, flow):
        if v == t:
            return flow
        links_v = self.links[v]
        for i in range(self.progress[v], len(links_v)):
            self.progress[v] = i
            cap, to, rev = link = links_v[i]
            if cap == 0 or self.depth[v] >= self.depth[to]:
                continue
            d = self.dfs(to, t, min(flow, cap))
            if d == 0:
                continue
            link[0] -= d
            self.links[to][rev][0] += d
            return d
        return 0

    def max_flow(self, s, t):
        flow = 0
        while True:
            self.bfs(s)
            if self.depth[t] < 0:
                return flow
            self.progress = [0] * self.n
            current_flow = self.dfs(s, t, float('inf'))
            while current_flow > 0:
                flow += current_flow
                current_flow = self.dfs(s, t, float('inf'))


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

vertices = {}  # {i,j: 頂点番号, 周囲の黒, 周囲の白個数, [周囲の'?'の(i,j)]}
fixed_zebra = 0
for i, row in enumerate(field):
    for j, c in enumerate(row):

        def register(ni, nj, b, w, ques):
            if field[ni][nj] == 'B':
                b += 1
            elif field[ni][nj] == 'W':
                w += 1
            else:
                ques.append((ni, nj))
            return b, w


        b, w = 0, 0
        ques = []

        if i > 0:
            b, w = register(i - 1, j, b, w, ques)
        if i < n - 1:
            b, w = register(i + 1, j, b, w, ques)
        if j > 0:
            b, w = register(i, j - 1, b, w, ques)
        if j < n - 1:
            b, w = register(i, j + 1, b, w, ques)

        if c == 'B':
            fixed_zebra += w
        elif c == 'W':
            fixed_zebra += b
        else:
            v = len(vertices)
            vertices[i, j] = [v, b, w, ques]

fixed_zebra //= 2

mf = Dinic(len(vertices) + 2)
s = len(vertices)
t = len(vertices) + 1
geta0 = 0
geta1 = 0
for (i, j), (v, b, w, ques) in vertices.items():
    geta0 += b + w
    geta1 += len(ques)
    if (i + j) % 2 == 0:
        mf.add_link(s, v, w)
        mf.add_link(v, t, b)
    else:
        mf.add_link(s, v, b)
        mf.add_link(v, t, w)
    for ti, tj in ques:
        u = vertices[ti, tj][0]
        mf.add_link(v, u, 1)

f = mf.max_flow(s, t)

print(fixed_zebra + geta0 + geta1 // 2 - f)