ABC300 F問題 More Holidays

atcoder.jp

できるだけ長く連続した'o' の長さを求める問題ですが、長さを求めるためには最初の'o' の位置 と最後の'o'の位置 から と考えればよいです。
'o'が連続する連続部分文字列をできるだけ長くするためには、最初の'o'は文字列の先頭あるいは'x'の次の文字となります。最初の'o'の位置から個の'x'を'o'に変えます。
文字列の先頭からの場合、最後の'o'は 個目の'x'の一つ前になります。最初の'o'が 個目の'x'の次の文字の場合、最後の'o'は 個目の'x'の一つ前になります。
文字列は、を個連結したものなので、最初の'o'の一つ前の'x'の選び方は、先頭の内だけループして調べれば十分です。
最後の'x'の位置は、何個目のの何番目の'x'か、から計算します。求めた位置が全体の文字列の長さを超えていれば、最後の'o'の位置を とします。

コード例 (Julia)

function solve()

  # 入力
  readInts() =  parse.(Int,split(readline()))
  readInt()  =  parse(Int,readline())

  N,M,K = readInts()
  S = readline()

  X = Vector{Int}()

  # S 内の 'x' の位置
  for i = 1:N
    if S[i] == 'x'
      push!(X,i)
    end
  end

  # S 内の 'x' の個数
  nx = length(X)

  ans = 0

  for i = 0:nx
    # 連続する 'o' の先頭
    head = 1
    if i > 0
      head = X[i] + 1
    end

    # 'o' に変えるのは 'x' の何個目までか
    # S を d 回繰り返した後の r 個目
    d,r = divrem( i + K, nx )

    # 連続する 'o' の最後
    tail = d * N + X[r+1] - 1
    if tail > N * M
      tail = N * M
    end

    if ans < tail - head + 1
      ans = tail - head + 1
    end
  end

  println(ans)

end  # function solve

# main
solve()