Submission #27567233

Source Code Expand

# frozen_string_literal: true

# ref:https://atcoder.jp/contests/abc229/submissions/27528242
# rubyはstringを比べるより数字またはシンボルの方が早いらしいのでバイト数に変換。
INPUT_BYTES = gets.chomp.bytes
ALLOWABLE_DOT_COUNT = gets.to_i
# 問題文は「連続した文字列を選択する場合、最長でいくつか。ただし選択文字列には.を規定個数までしか入れられないものとする」と言い換えられる
# この場合、選択文字列は左右どちらとも.に当たるまで広げるのが最適。一つ外側にXがあるのに広げない理由がない
# 逆に言うと、文字列の左右の外側には.があるかもしくはS自体がないかのどちらか
# 配列の一個前に.があると仮定する
dot_indexes = [-1]
# 暫定回答
buffer_answer = 0
# .のバイト数
DOT_BYTE = ".".bytes[0]
INPUT_BYTES.each_with_index do |tmp_byte, tmp_index|
  # Xだった場合は無視
  next unless tmp_byte == DOT_BYTE

  # .だった場合はキューに追加
  dot_indexes << tmp_index
  # キュー内の.がまだ溢れていない場合も無視
  next if dot_indexes.size <= ALLOWABLE_DOT_COUNT + 1

  # 選択文字列の左外にある.のインデックスは、今キューから押し出された値
  left_out_dot_index = dot_indexes.shift
  # つまり選択文字列の開始インデックスはこれの一個後
  array_start_index = left_out_dot_index + 1
  # 選択文字列の右外にある.のインデックスは、たった今tmp_indexとしてキューに追加した値
  right_out_dot_index = dot_indexes[-1]
  # つまり選択文字列の終了インデックスはこれの一個前
  array_goal_index = right_out_dot_index - 1
  # 選択文字列の長さは終了地点 - 開始地点 + 1
  tmp_array_length = array_goal_index - array_start_index + 1
  # これが暫定回答より長ければ更新
  buffer_answer = tmp_array_length if tmp_array_length > buffer_answer
end
# Sの右端がXだった場合に対応できないので最後にもう一回
# 開始位置のとり方はループ内と一緒
left_out_dot_index = dot_indexes.shift
array_start_index = left_out_dot_index + 1
# 終了位置はSの右端
array_goal_index = INPUT_BYTES.size - 1
# これ以降はループ内と一緒
tmp_array_length = array_goal_index - array_start_index + 1
buffer_answer = tmp_array_length if tmp_array_length > buffer_answer

puts buffer_answer

Submission Info

Submission Time
Task D - Longest X
User HalMat
Language Ruby (2.7.1)
Score 400
Code Size 2517 Byte
Status AC
Exec Time 87 ms
Memory 17876 KiB

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 400 / 400
Status
AC × 2
AC × 37
Set Name Test Cases
Sample example0.txt, example1.txt
All 000.txt, 001.txt, 002.txt, 003.txt, 004.txt, 005.txt, 006.txt, 007.txt, 008.txt, 009.txt, 010.txt, 011.txt, 012.txt, 013.txt, 014.txt, 015.txt, 016.txt, 017.txt, 018.txt, 019.txt, 020.txt, 021.txt, 022.txt, 023.txt, 024.txt, 025.txt, 026.txt, 027.txt, 028.txt, 029.txt, 030.txt, 031.txt, 032.txt, 033.txt, 034.txt, example0.txt, example1.txt
Case Name Status Exec Time Memory
000.txt AC 60 ms 14188 KiB
001.txt AC 57 ms 14144 KiB
002.txt AC 60 ms 14364 KiB
003.txt AC 56 ms 14324 KiB
004.txt AC 79 ms 17832 KiB
005.txt AC 73 ms 16212 KiB
006.txt AC 55 ms 14184 KiB
007.txt AC 57 ms 14184 KiB
008.txt AC 80 ms 16112 KiB
009.txt AC 78 ms 17208 KiB
010.txt AC 86 ms 16088 KiB
011.txt AC 80 ms 16576 KiB
012.txt AC 78 ms 16084 KiB
013.txt AC 75 ms 16132 KiB
014.txt AC 73 ms 15964 KiB
015.txt AC 68 ms 15648 KiB
016.txt AC 73 ms 16204 KiB
017.txt AC 72 ms 16084 KiB
018.txt AC 68 ms 16020 KiB
019.txt AC 69 ms 15516 KiB
020.txt AC 67 ms 15312 KiB
021.txt AC 87 ms 16332 KiB
022.txt AC 86 ms 16312 KiB
023.txt AC 79 ms 16288 KiB
024.txt AC 72 ms 16260 KiB
025.txt AC 73 ms 16248 KiB
026.txt AC 78 ms 17876 KiB
027.txt AC 79 ms 17328 KiB
028.txt AC 75 ms 17484 KiB
029.txt AC 75 ms 16468 KiB
030.txt AC 72 ms 16204 KiB
031.txt AC 78 ms 16260 KiB
032.txt AC 75 ms 16484 KiB
033.txt AC 79 ms 16196 KiB
034.txt AC 74 ms 16484 KiB
example0.txt AC 55 ms 14116 KiB
example1.txt AC 57 ms 14224 KiB