提出 #76656226

ソースコード 拡げる

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class FastScanner
  def initialize
    @data = STDIN.read
    @idx = 0
    @n = @data.length
  end
  def next_token
    data = @data
    n = @n
    i = @idx
    i += 1 while i < n && data.getbyte(i) <= 32
    j = i
    j += 1 while j < n && data.getbyte(j) > 32
    @idx = j
    data[i...j]
  end
end
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

class FastScanner
  def initialize
    @data = STDIN.read
    @idx = 0
    @n = @data.length
  end

  def next_token
    data = @data
    n = @n
    i = @idx
    i += 1 while i < n && data.getbyte(i) <= 32

    j = i
    j += 1 while j < n && data.getbyte(j) > 32

    @idx = j
    data[i...j]
  end
end

def solve_case(s, k)
  k1 = k + 1
  inf = 1 << 60

  # state 0: 末尾が使えない
  # state 1: 末尾が "A"
  # state 2: 末尾が "AB"
  dp = Array.new(3 * k1, inf)
  ndp = Array.new(3 * k1, inf)

  dp[0] = 0

  # 元の文字列側で、直前 2 文字をカテゴリとして持つ
  # 0=A, 1=B, 2=C, 3=その他
  prev2 = 3
  prev1 = 3

  i = 0
  n = s.length

  while i < n
    byte = s.getbyte(i)

    oc =
      if byte == 65       # A
        0
      elsif byte == 66    # B
        1
      elsif byte == 67    # C
        2
      else
        3
      end

    # 元の S で、この位置を右端として ABC が存在するか
    old = (prev2 == 0 && prev1 == 1 && oc == 2) ? 1 : 0

    cost_a = (oc == 0 ? 0 : 1)
    cost_b = (oc == 1 ? 0 : 1)
    cost_c = (oc == 2 ? 0 : 1)
    cost_x = (oc == 3 ? 0 : 1)

    ndp.fill(inf)

    st = 0
    while st < 3
      base = st * k1

      # B を選んだときの遷移先
      b_base = (st == 1 ? 2 * k1 : 0)

      # C を選んだとき、今 ABC ができるか
      add_c = (st == 2 ? 1 : 0)

      d = 0
      while d < k1
        cur = dp[base + d]

        # A, B, その他は新しい ABC を作らない
        nd = d - old
        if nd >= 0
          # A を選ぶ
          v = cur + cost_a
          idx = k1 + nd
          ndp[idx] = v if v < ndp[idx]

          # B を選ぶ
          v = cur + cost_b
          idx = b_base + nd
          ndp[idx] = v if v < ndp[idx]

          # その他を選ぶ
          v = cur + cost_x
          idx = nd
          ndp[idx] = v if v < ndp[idx]
        end

        # C を選ぶ
        nd = d + add_c - old
        if nd >= 0 && nd < k1
          v = cur + cost_c
          idx = nd
          ndp[idx] = v if v < ndp[idx]
        end

        d += 1
      end

      st += 1
    end

    dp, ndp = ndp, dp

    prev2 = prev1
    prev1 = oc

    i += 1
  end

  ans = dp[k]
  v = dp[k1 + k]
  ans = v if v < ans
  v = dp[2 * k1 + k]
  ans = v if v < ans

  ans >= inf ? -1 : ans
end

fs = FastScanner.new
first = fs.next_token
exit if first.nil? || first.empty?

t = first.to_i
out = []

t.times do
  a = fs.next_token
  b = fs.next_token

  # 通常は S K を想定。
  # もし K S の形でも読めるようにしてあります。
  if a.getbyte(0) >= 48 && a.getbyte(0) <= 57
    k = a.to_i
    s = b
  else
    s = a
    k = b.to_i
  end

  out << solve_case(s, k).to_s
end

puts out.join("\n")

提出情報

ジャッジ結果