キーエンスプログラミングコンテスト2021-Nov. (AtCoder Beginner Contest 227) E,F,G,H問題メモ

from collections import defaultdict

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

indices = [[], [], []]
for c in s:
    if c == 'K':
        indices[0].append((len(indices[1]), len(indices[2])))
    elif c == 'E':
        indices[1].append((len(indices[0]), len(indices[2])))
    else:
        indices[2].append((len(indices[0]), len(indices[1])))

dp = defaultdict(int)
dp[0, 0, 0, 0] = 1

for i in range(len(s)):
    new = defaultdict(int)
    for (ck, ce, cy, t), pat in dp.items():
        if ck < len(indices[0]):
            me, my = indices[0][ck]
            cost = max(0, me - ce) + max(0, my - cy)
            if t + cost <= k:
                new[ck + 1, ce, cy, t + cost] += pat

        if ce < len(indices[1]):
            mk, my = indices[1][ce]
            cost = max(0, mk - ck) + max(0, my - cy)
            if t + cost <= k:
                new[ck, ce + 1, cy, t + cost] += pat

        if cy < len(indices[2]):
            mk, me = indices[2][cy]
            cost = max(0, mk - ck) + max(0, me - ce)
            if t + cost <= k:
                new[ck, ce, cy + 1, t + cost] += pat

    dp = new

print(sum(dp.values()))

import os
import sys

import numpy as np


def solve(h, w, k, field):
    INF = 1 << 60
    ans = INF

    for thr in np.unique(field):

        dp = np.full((h, w, k + 1), INF, dtype=np.int64)
        if field[0, 0] <= thr:
            dp[0, 0, 0] = 0
        if field[0, 0] >= thr:
            dp[0, 0, 1] = field[0, 0]

        for i in range(h):
            for j in range(w):
                for p in range(k + 1):
                    if dp[i, j, p] == INF:
                        continue

                    if i < h - 1:
                        if field[i + 1, j] <= thr:
                            dp[i + 1, j, p] = min(dp[i + 1, j, p], dp[i, j, p])
                        if p < k and field[i + 1, j] >= thr:
                            dp[i + 1, j, p + 1] = min(dp[i + 1, j, p + 1], dp[i, j, p] + field[i + 1, j])

                    if j < w - 1:
                        if field[i, j + 1] <= thr:
                            dp[i, j + 1, p] = min(dp[i, j + 1, p], dp[i, j, p])
                        if p < k and field[i, j + 1] >= thr:
                            dp[i, j + 1, p + 1] = min(dp[i, j + 1, p + 1], dp[i, j, p] + field[i, j + 1])

        ans = min(ans, dp[h - 1, w - 1, k])

    return ans


SIGNATURE = '(i8,i8,i8,i8[:,:])'
if sys.argv[-1] == 'ONLINE_JUDGE':
    from numba.pycc import CC

    cc = CC('my_module')
    cc.export('solve', SIGNATURE)(solve)
    cc.compile()
    exit()

if os.name == 'posix':
    # noinspection PyUnresolvedReferences
    from my_module import solve
else:
    from numba import njit

    solve = njit(SIGNATURE, cache=True)(solve)
    print('compiled', file=sys.stderr)

h, w, k, *field = map(int, sys.stdin.buffer.read().split())
field = np.array(field, dtype=np.int64).reshape((h, w))

ans = solve(h, w, k, field)
print(ans)

def get_primes(n):
    """ nまでの素数リスト """
    candidates = [0, 1] * (n // 2 + 1)
    if n % 2 == 0:
        candidates.pop()
    candidates[1] = 0
    candidates[2] = 1
    for p in range(3, int(n ** 0.5) + 1, 2):
        if candidates[p]:
            for m in range(p * p, n + 1, 2 * p):
                candidates[m] = 0
    return [p for p, b in enumerate(candidates) if b]


n, k = map(int, input().split())
MOD = 998244353

primes = get_primes(10 ** 6)

offset = n - k + 1
factor_remaining = list(range(offset, n + 1))

ans = 1
for p in primes:
    if p > n:
        break

    tmp = 0
    q = p
    while q <= n:
        s = ((offset - 1) // q + 1) * q - offset
        for i in range(s, k, q):
            factor_remaining[i] //= p
            tmp += 1
        q *= p

    q = p
    while q <= k:
        tmp -= k // q
        q *= p

    ans = ans * (tmp + 1) % MOD

ans *= pow(2, sum(r > 1 for r in factor_remaining), MOD)
ans %= MOD

print(ans)

⓪→①の辺を使わないで条件を満たすルートで、 ⓪→①を代わりに使う形に変換できないものを考え、それが存在しないことを示す。

グリッドの回転・反転、辺の向きの一斉反転を使えば、この1箇所だけ証明できれば十分。

以下のような図を使って、使わないことが確定した辺、使うことが確定した辺を決めていく。

    →    →      これ以降の図で、対応する位置に
 ⓪ ← ① ← ②   ・矢印が書かれている: 使うことが確定した辺
↑↓  ↑↓  ↑↓  ・×印が書かれている: 使わないことが確定した辺
 ③ → ④ → ⑤   ・何も書かれていない: 未決定の辺
    ←    ←      とする。

• 各頂点の入出次数を変えてはいけない
• 連結でなくなってはいけない
• 既に存在する、他の外周辺①→②や②→⑤などを代わりに失ってはいけない

以上を守って辺を変えても、⓪→①を使うようにできないものを考える。

    ×      
 ⓪    ①    ②     ⓪→①を使わないとした場合、
  ↓                Ai >= 1より⓪から1本は辺が出るので、
 ③    ④    ⑤     ⓪→③の辺を使うことが確定する

【①→⓪を使う場合】
    ×
 ⓪ ← ①(←)②     現在の状態は条件を満たす（オイラー路を構築できる）ので、
  ↓       (↑)     ①→⓪を通って①に戻る、交差しない閉路が必ず存在する。
 ③(→)④(→)⑤     （図は一例）
 
    →    →
 ⓪    ①    ②     それを全て反転させることで⓪→①の辺を作れる。
↑          ↓      反時計回りを時計回りに変換するので、他の外周辺を失うことはない。
 ③    ④    ⑤
    ←    ←

よって、①→⓪の辺も使えないことがわかる。そして③→⓪の辺を使うことが確定する。
    ×      
 ⓪ × ①    ②     
↑↓                
 ③    ④    ⑤     

【④→①を使う場合】
    ×      
 ⓪ × ①    ②     
↑↓  ↑            ⓪→③ と ④→①のように互い違いの関係にある平行な2辺は、
 ③    ④    ⑤     

    →      
 ⓪ × ①    ②     こう繋ぎ替えられる。
↑                  つなぎ替えることで連結で無くなる可能性を考慮しなければならないが、
 ③    ④    ⑤     ③→⓪を使うことが確定しているため、連結は保たれる。
    ←

【①→④を使う場合】
    ×      
 ⓪ ← ①    ②     同様に、こう繋ぎ替えられる。
  ↓                更に先ほどの、閉路の辺反転を使うことで、⓪→①の辺を作れる。
 ③ → ④    ⑤     一時的に外周辺③→⓪を失うが、これを含めて辺反転させればよい。

よって、①→④、④→①の辺も使えないとなる。
すると、①を他と連結にするためには、②、⑤と連結するしか無くなる。
    ×    →
 ⓪ × ① ← ②     
↑↓  ××  ↑↓    
 ③    ④    ⑤     

以下、同様の議論が④⇄⑤にも適用され、これらの辺も使えないとなる。
すると⑤は連結を保つため、⑧、⑦と連結になる。
    ×    →
 ⓪ × ① ← ②     
↑↓  ××  ↑↓    
 ③    ④ × ⑤     
            ↑↓
       ⑦ → ⑧
          ←
これを繰り返すと、④⇄⑦、③⇄⑦ の辺も使えなくなり、④が孤立する。
よって矛盾する。

from collections import deque


class Dinic:
    """
    Usage:
       mf = Dinic(n)
    -> mf.add_link(from, to, capacity)
    -> mf.max_flow(source, target)
    """

    def __init__(self, n):
        self.n = n
        self.links = [[] for _ in range(n)]

    def add_link(self, from_, to, capacity):
        self.links[from_].append([capacity, 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)
        return depth

    def dfs(self, s, t, depth, progress, link_counts):
        links = self.links
        stack = [s]

        while stack:
            v = stack[-1]
            if v == t:
                break
            for i in range(progress[v], link_counts[v]):
                progress[v] = i
                cap, to, rev = links[v][i]
                if cap == 0 or depth[v] >= depth[to] or progress[to] >= link_counts[to]:
                    continue
                stack.append(to)
                break
            else:
                progress[v] += 1
                stack.pop()
        else:
            return 0

        f = 1 << 60
        fwd_links = []
        bwd_links = []
        for v in stack[:-1]:
            cap, to, rev = link = links[v][progress[v]]
            f = min(f, cap)
            fwd_links.append(link)
            bwd_links.append(links[to][rev])

        for link in fwd_links:
            link[0] -= f

        for link in bwd_links:
            link[0] += f

        return f

    def max_flow(self, s, t):
        link_counts = list(map(len, self.links))
        flow = 0
        while True:
            depth = self.bfs(s)
            if depth[t] < 0:
                break
            progress = [0] * self.n
            current_flow = self.dfs(s, t, depth, progress, link_counts)
            while current_flow > 0:
                flow += current_flow
                current_flow = self.dfs(s, t, depth, progress, link_counts)
        return flow


def solve(grid):
    if sum(grid[0::2]) != sum(grid[1::2]):
        return False

    path = [[i] for i in range(9)]

    for i in range(9):
        if i != 4:
            grid[i] -= 1

    mxf = Dinic(11)
    s = 9
    t = 10
    for i in range(9):
        if i % 2 == 0:
            mxf.add_link(s, i, grid[i])
            if i < 6:
                mxf.add_link(i, i + 3, 100)
            if i % 3 < 2:
                mxf.add_link(i, i + 1, 100)
        else:
            mxf.add_link(i, t, grid[i])
            if i < 6:
                mxf.add_link(i + 3, i, 100)
            if i % 3 < 2:
                mxf.add_link(i + 1, i, 100)

    flow = mxf.max_flow(s, t)

    if flow != sum(grid[0::2]):
        return False

    for i in (1, 3, 5, 7):
        for link in mxf.links[i]:
            j = link[1]
            if j == t or link[0] == 0:
                continue
            path[i].extend([j, i] * link[0])
            grid[i] -= link[0]

    whole_path = []
    for i in (0, 1, 2, 5, 8, 7, 6, 3):
        whole_path.extend(path[i])
    whole_path.append(0)

    ans = []
    for i, j in zip(whole_path, whole_path[1:]):
        if i - j == 1:
            ans.append('L')
        elif i - j == -1:
            ans.append('R')
        elif i - j == 3:
            ans.append('U')
        elif i - j == -3:
            ans.append('D')
        else:
            raise AssertionError

    return ''.join(ans)


grid = []
for _ in range(3):
    grid.extend(map(int, input().split()))

ans = solve(grid)
if ans == False:
    print('NO')
else:
    print(ans)