F - More Holidays Editorial by cirno3153

分かりやすさのため、 \(S\) は0-indexedで扱います。

oのみからなる連続部分文字列の長さとして達成可能な最大値を取る区間を \([l, r)\) とします。 この時、 \(0 \leq l < N\) としても一般性を失いません*1。

そこで、 \(l\) を全探索することとします。 この時、以下の長さ \(N+1\) の補助配列を作ることで \(O(1)\) で \(r\) を見つけることができます。

  • \(C_i\) : \([0, i)\) 文字目に含まれるxの個数(すなわち累積和)
  • \(M_i\) : xを \(i\) 個までoに変えることができる時、先頭から最大何文字までoが連続するか

まず、 \(C_N - C_l > K\) だとします。この時、 \(r < N\) であることが分かり、この場合は \(r=M_{K + C_l}\) となります。

次に、\(C_N - C_l \leq K\) だとします。この時、まず長さ \(N-l\) を伸ばすことで右端に到達し、次に \(\frac{K-(C_N - C_l)}{C_N}\) 個の \(S\) を覆い、最後に残りを埋めます。 これは、残りの変換回数を \(t (=K-(C_N - C_l) \bmod C_N)\) とすると \(M_t\) がそのまま答えとなります。

この計算で答えが \(NM-l\) を超える時、それは全部oにできたということなので \(NM-l\) で \(\min\) を取ることを忘れないでください。

コード例

import java.util.*

fun main() {
  val sc = Scanner(System.`in`)
  val N = sc.nextInt()
  val M = sc.nextInt()
  val K = sc.nextLong()
  val S = sc.next()
  
  val cumsum = IntArray(N + 1) // cumsum[i]: [0, i)の区間に含まれる'x'の個数
  val maxuse = IntArray(N + 1) // maxuse[i]: 'x'をi個まで'o'に変える時、先頭から'o'が最大何個連続するか
  for (i in 1..N) {
    cumsum[i] = cumsum[i - 1] + if (S[i - 1] == 'x') 1 else 0
    maxuse[cumsum[i]] = i
  }
  val xCount = cumsum[N] // Sに含まれる'x'の個数
  println((0 until N).map { l -> // lを左端として、右端をどこまで伸ばせるか
    val toRight = xCount - cumsum[l] // 右端まで行く為に変える'x'の個数
    if (toRight > K) maxuse[(K + cumsum[l]).toInt()] - l.toLong() // 右端に行けないなら、答えはmaxuseから求まる
    else {
      val repeat = (K - toRight) / xCount // 完全に覆えるSの個数
      N - l + Math.min(N * (M - 1L), N * repeat + maxuse[(K - toRight - xCount * repeat).toInt()])
    }
  }.max()!!)
}

posted:
last update: