CodeQUEEN 2026 予選 (AtCoder Beginner Contest 462)E,F問題メモ

CodeQUEEN 2026 予選 (AtCoder Beginner Contest 462)

今年もコークイの時期がやって参りました。（誰も使ってない略称）

E - Alternating Costs

問題文

整数 $A,B,X,Y$ が与えられます。
二次元平面上にコマが置かれています。はじめコマは座標 $(0,0)$ にあります。
あなたは、上下左右に1マス分コマを動かす操作を $0$ 回以上何回でも行うことができます。
$k$ 回目 $(k \geq 1)$ に行う操作にかかるコストは $k$ の偶奇によって異なり、それぞれ以下の通りです：
- $k$ が奇数のとき：
  - 横移動（$(x-1,y),(x+1,y)$ への移動）のコストは $A$
  - 縦移動（$(x,y-1),(x,y+1)$ への移動）のコストは $B$
- $k$ が偶数のとき：
  - 横移動（$(x-1,y),(x+1,y)$ への移動）のコストは $B$
  - 縦移動（$(x,y-1),(x,y+1)$ への移動）のコストは $A$
コマを座標 $(X,Y)$ に移動させるために必要なコストの総和の最小値を求めてください。

$T$ 個のテストケースが与えられるので、それぞれについて答えを求めてください。

制約

$1\le T\le 2\times 10^5$
$1\le A,B\le 10^9$
$-10^9\le X,Y\le 10^9$
入力される値は全て整数

解法

とりあえず、答えが同じになる対称的な位置関係の入力は、パターン数を減らす。
$X,Y$ は絶対値を取る。また $A \gt B$ の場合は $(A,B),(X,Y)$ をそれぞれ45度線で反転させる（$(B,A),(Y,X)$ とする）。

これにより、目標は第1象限にあり、$A \le B$（奇数回目は横移動が安く、偶数回目は縦移動が安くなる）という状況に統一できる。

まずは $d=\min(X,Y)$ として、$(d,d)$ までは安い方の移動（→↑の繰り返し）で行ける。

その後、$X \gt Y$ なら、右方向に追加で動かなければならない。ここに2パターンの動きがある。

→→
- 常に右に動く。偶数回目はコストが高いが受け入れる。2マス右に進むのに $A+B$
- 最後、1マス余ったら追加で $A$
→↓→↑
- 回数はかさむが、常にコストの低い移動方法を使う。2マス右に進むのに $4A$
- 最後、1マス余ったら追加で $A$

$X \lt Y$ なら、上方向に追加で動かなければならない。同様に、

↑↑
- 常に上に動く。奇数回目はコストが高いが受け入れる。2マス上に進むのに $B+A$
- 最後、1マス余ったら追加で $B$
→↑←↑
- 回数はかさむが、常にコストの低い移動方法を使う。2マス上に進むのに $4A$
- 最後、1マス余ったら追加で $3A$

となる。まぁ、明らかだが $B$ と $3A$ の大小関係で最適な方が決まる。

Python3

def solve(a, b, x, y):
    x = abs(x)
    y = abs(y)
    if a == b:
        return (x + y) * a
    if a > b:
        x, y = y, x
        a, b = b, a

    ans_base = min(x, y) * a * 2
    if x < y:
        d = y - x
        ans1 = ans_base
        ans1 += d // 2 * (a + b)
        if d % 2 == 1:
            ans1 += b

        ans2 = ans_base
        ans2 += d // 2 * (a * 4)
        if d % 2 == 1:
            ans2 += min(a * 3, b)

    elif x > y:
        d = x - y
        ans1 = ans_base
        ans1 += d // 2 * (a + b)
        if d % 2 == 1:
            ans1 += a

        ans2 = ans_base
        ans2 += d // 2 * (a * 4)
        if d % 2 == 1:
            ans2 += a

    else:
        ans1 = ans2 = ans_base

    ans = min(ans1, ans2)
    return ans


t = int(input())
for _ in range(t):
    a, b, x, y = list(map(int, input().split()))
    ans = solve(a, b, x, y)
    print(ans)

F - More ABC

問題文

英大文字のみからなる文字列 $S$ が与えられます。
高橋君の目標は、$S$ の文字のうちいくつかを置換することによって、$S$ が ABC を部分文字列として含む個数をちょうど $K$ 個増やすことです。
このようなことが可能か判定し、可能な場合は目標を達成するために高橋君が最低何文字置換する必要があるか求めてください。
$T$ 個のテストケースが与えられるので、それぞれについて答えを求めてください。

制約

$1\leq T\leq 10^5$
$S$ は英大文字のみからなる長さ $3$ 以上 $3\times 10^5$ 以下の文字列
$1\leq K \leq 10$
それぞれの入力において、各テストケースの $S$ の長さの総和は $3\times 10^5$ 以下である。
$T,K$ は整数

解法

「$K$ 個にする」でなくて「$K$ 個増やす」というのが特徴的。かつ $K$ が小さい。
既存のABCをいったん崩し、位置をずらしてABCを2個作る、というようなこともあり得るのが難しい。

もし、$S$ に最初からあるABCの個数を $d$ として、「含まれるABCを $d+K$ 個にする最小コスト」というDPを組むのだったら、こうなる。

$\mathrm{DP}_{仮}[i,j,k]:=$
- $i$ 文字目まで決めて、
- 決めた部分の末尾が以下で、
  - $j=0$: 下記のどれでもない
  - $j=1$: 'A'である
  - $j=2$: 'AB'である
- できたABCが $k$ 個の場合に、変更した文字の最小個数

ABまで進めて次にCを置いたときに $k$ を1つ増やせば、適切に、できたABCの個数を数えながら遷移できる。

ただし、これは $k$ の範囲（$d+K$）が $10^5$ 近くになり得るため、$i$ の範囲と合わせて $O(|S|^2)$ となり、無理。

ここで、“含まれる” ではなく “元から増えた” 個数を $k$ とするDPを組めれば、$O(|S|K)$ でよくなり間に合いそう。
だが、それをするには、状態の持たせ方と遷移が複雑になる。

$\mathrm{DP}[i,j,k]:=$
- $i$ 文字目まで決めて、
- 決めた部分の末尾が以下で、
  - $j=0$: 下記のどれでもない
  - $j=1$: 元からある'A'である
  - $j=2$: 変更した'A'である
  - $j=3$: いずれも元からある'AB'である
  - $j=4$: いずれかは変更した'AB'である
- 「1箇所でもどこかを変更することで作られたABC」が $k$ 個の場合に、変更した文字の最小個数

「変更したかどうか」という区別が増えた。
これは、完成したABCが、元からあったものか、変更によって作られたものかで遷移が変わるためである。元から合ったABCが、変更されないまま完成したとて、$k$ を増やしてはいけない。

また、$k$ は負値 $-1$ も取り得る。
既存のABCを壊す変更をおこなった場合は、個数が元から減るためである。

ただし、負値になるとしても $-1$ まで考慮しておけば十分と言える。
既存のABCを壊す目的は、当然、より多くのABCを作るためであり、そのためには AABCBC→ABCABC のように、壊したABCの中で、新たなABCの1つが完成していなければならない。
したがって、同時に2つ以上のABCを壊す（その過程で新たなABCが1つも完成していない）という状況は想定しなくてよい。

これを元に注意深く遷移を書けば、$\mathrm{DP}[N,*,K]$ の最小値が答えとなる。状態数が $5$ とそこそこ多く、また既存のABCを壊すかの判定まで入ってくるので、漏れたり誤記しやすい。

Python3

def solve(s, k):
    INF = 1 << 60
    dp = [[INF] * (k + 2) for _ in range(5)]
    dp[0][0] = 0
    # state: ここまでの末尾との一致具合
    #   0: ABCとのprefixとの一致無し
    #   1: 改変無く A と一致
    #   2: 改変して A と一致
    #   3: 改変無く AB と一致
    #   4: どちらか改変して AB と一致

    n = len(s)
    for i in range(n):
        c = s[i]
        ndp = [[INF] * (k + 2) for _ in range(5)]
        if c == 'A':
            # 改変した場合既存のを壊すか
            destroy = i < n - 2 and s[i + 1] == 'B' and s[i + 2] == 'C'
            for j in range(-1, k + 1):
                # 変えない
                ndp[1][j] = min(ndp[1][j], dp[0][j], dp[1][j], dp[2][j], dp[3][j], dp[4][j])
                # 変える
                if destroy:
                    if j > -1:
                        ndp[4][j - 1] = min(ndp[4][j - 1], dp[1][j] + 1, dp[2][j] + 1)  # Bにかえる
                    ndp[0][j] = min(ndp[0][j], dp[3][j] + 1, dp[4][j] + 1)  # Cにかえる
                else:
                    ndp[4][j] = min(ndp[4][j], dp[1][j] + 1, dp[2][j] + 1)  # Bにかえる
                    if j < k:
                        ndp[0][j + 1] = min(ndp[0][j + 1], dp[3][j] + 1, dp[4][j] + 1)  # Cにかえる
        elif c == 'B':
            destroy = 0 < i < n - 1 and s[i - 1] == 'A' and s[i + 1] == 'C'
            for j in range(-1, k + 1):
                # 変えない
                ndp[0][j] = min(ndp[0][j], dp[0][j], dp[3][j], dp[4][j])
                ndp[3][j] = min(ndp[3][j], dp[1][j])
                ndp[4][j] = min(ndp[4][j], dp[2][j])
                # 変える
                if destroy:
                    if j > -1:
                        ndp[2][j - 1] = min(ndp[2][j - 1], dp[1][j] + 1)  # Aにかえる
                    ndp[2][j] = min(ndp[2][j], dp[0][j] + 1, dp[3][j] + 1, dp[4][j] + 1)  # Aにかえる
                else:
                    ndp[2][j] = min(ndp[2][j], dp[0][j] + 1, dp[1][j] + 1, dp[2][j] + 1, dp[3][j] + 1,
                                    dp[4][j] + 1)  # Aにかえる
                if j < k:
                    ndp[0][j + 1] = min(ndp[0][j + 1], dp[3][j] + 1, dp[4][j] + 1)  # Cにかえる
        elif c == 'C':
            destroy = 1 < i and s[i - 2] == 'A' and s[i - 1] == 'B'
            for j in range(-1, k + 1):
                # 変えない
                ndp[0][j] = min(ndp[0][j], dp[0][j], dp[1][j], dp[2][j], dp[3][j])
                if j < k:
                    ndp[0][j + 1] = min(ndp[0][j + 1], dp[4][j])
                # 変える
                if destroy:
                    if j > -1:
                        ndp[2][j - 1] = min(ndp[2][j - 1], dp[3][j] + 1)  # Aにかえる
                    ndp[2][j] = min(ndp[2][j], dp[0][j] + 1, dp[1][j] + 1, dp[2][j] + 1, dp[4][j] + 1)  # Aにかえる
                    ndp[4][j] = min(ndp[4][j], dp[1][j] + 1, dp[2][j] + 1)  # Bにかえる
                else:
                    ndp[2][j] = min(ndp[2][j], dp[0][j] + 1, dp[1][j] + 1, dp[2][j] + 1, dp[3][j] + 1,
                                    dp[4][j] + 1)  # Aにかえる
                    ndp[4][j] = min(ndp[4][j], dp[1][j] + 1, dp[2][j] + 1)  # Bにかえる
        else:
            for j in range(-1, k + 1):
                # 変えない
                ndp[0][j] = min(ndp[0][j], dp[0][j], dp[1][j], dp[2][j], dp[3][j], dp[4][j])
                # 変える
                ndp[2][j] = min(ndp[2][j], dp[0][j] + 1, dp[1][j] + 1, dp[2][j] + 1, dp[3][j] + 1,
                                dp[4][j] + 1)  # Aにかえる
                ndp[4][j] = min(ndp[4][j], dp[1][j] + 1, dp[2][j] + 1)  # Bにかえる
                if j < k:
                    ndp[0][j + 1] = min(ndp[0][j + 1], dp[3][j] + 1, dp[4][j] + 1)  # Cにかえる
        dp = ndp
        # print(f'{i=} {s[i]=}')
        # for j in range(5):
        #     print(f'{j=} {dp[j]=}')

    ans = min(dp[state][k] for state in range(5))
    if ans == INF:
        ans = -1
    return ans


def naive(s, k):
    base = s.count('ABC')
    target = base + k
    INF = 1 << 60
    dp = [[INF] * (target + 1) for _ in range(3)]
    dp[0][0] = 0
    n = len(s)
    for i in range(n):
        ndp = [[INF] * (target + 1) for _ in range(3)]
        c = s[i]
        if c == 'A':
            for j in range(target + 1):
                ndp[1][j] = min(ndp[1][j], dp[0][j], dp[1][j], dp[2][j])
                ndp[2][j] = min(ndp[2][j], dp[1][j] + 1)
                if j < target:
                    ndp[0][j + 1] = min(ndp[0][j + 1], dp[2][j] + 1)
        elif c == 'B':
            for j in range(target + 1):
                ndp[0][j] = min(ndp[0][j], dp[0][j], dp[1][j], dp[2][j])
                ndp[1][j] = min(ndp[1][j], dp[0][j] + 1, dp[1][j] + 1, dp[2][j] + 1)
                ndp[2][j] = min(ndp[2][j], dp[1][j])
                if j < target:
                    ndp[0][j + 1] = min(ndp[0][j + 1], dp[2][j] + 1)
        elif c == 'C':
            for j in range(target + 1):
                ndp[0][j] = min(ndp[0][j], dp[0][j], dp[1][j], dp[2][j])
                ndp[1][j] = min(ndp[1][j], dp[0][j] + 1, dp[1][j] + 1, dp[2][j] + 1)
                ndp[2][j] = min(ndp[2][j], dp[1][j] + 1)
                if j < target:
                    ndp[0][j + 1] = min(ndp[0][j + 1], dp[2][j])
        else:
            for j in range(target + 1):
                ndp[0][j] = min(ndp[0][j], dp[0][j], dp[1][j], dp[2][j])
                ndp[1][j] = min(ndp[1][j], dp[0][j] + 1, dp[1][j] + 1, dp[2][j] + 1)
                ndp[2][j] = min(ndp[2][j], dp[1][j] + 1)
                if j < target:
                    ndp[0][j + 1] = min(ndp[0][j + 1], dp[2][j] + 1)
        dp = ndp
        # print(f'{i=} {s[i]=}')
        # print(f'{dp=}')

    ans = min(dp[state][target] for state in range(3))
    if ans == INF:
        ans = -1
    return ans


def check():
    # test = [
    #     ('XABCABCABCYZ', 1),
    #     ('XABCABCABCYZ', 2),
    #     ('AABCABCABCBC', 1),
    # ]
    import random
    n = 10
    test = []
    for _ in range(100000):
        s = ''.join(random.choices('ABCX', k=n))
        # k = random.choice([6, 7, 8, 9, 10])
        k = 1
        test.append((s, k))

    for s, k in test:
        ans1 = solve(s, k)
        ans2 = naive(s, k)
        if ans1 == ans2:
            continue
        print(f'=== NG === {ans1=} {ans2=}')
        print(s)
        print(k)
    print('FINISH')


# check()

t = int(input())
for _ in range(t):
    s = input()
    k = int(input())
    ans = solve(s, k)
    print(ans)

目次

CodeQUEEN 2026 予選 (AtCoder Beginner Contest 462)E,F問題メモ

E - Alternating Costs

問題文

制約

解法

F - More ABC

問題文

制約

解法