Ruby で解く AtCoder ABC 043 D - アンバランス (ARC 059 D)

はじめに

• AtCoder Problems の ABC042 以降の問題を解いています
• 勉強のために Ruby で解いています
  • 速度的な面で他の言語には劣りますが、あくまで勉強のためです

お題

• 今回のお題は、 ABC 043 Dのアンバランス という問題です
• 入力文字列の部分文字列がアンバランスかどうかを判定し、アンバランスなら具体的な区間を答えるというもの

考えたこと

• 何も考えずに作ろうとすると、時間計算量は$O(n^3)$になる
  • 部分文字列の列挙で$O(n^2)$
  • 判定で$O(n)$
• 位置を1つ示せば良い
  • 答えは複数あるのだが、少なくとも1つのアンバランスな区間を示せれば良い
• アンバランスな文字列は以下のパターンのどちらかを含む
  • 長さ2の"XX"というパターン
  • 長さ3の"XYX"というパターン
• 上記踏まえ、入力文字列を先頭から走査していき、走査位置と走査位置の1個先、2個先を見るだけで、アンバランスな部分文字列を含むか判定できるので、$O(n)$で求めることができる

コード

s = gets.chomp.chars
len = s.size
found = false

(0...len-1).each do |i|
  # 隣接する同じ文字のチェック
  if s[i] == s[i+1]
    puts "#{i+1} #{i+2}"
    found = true
    break
  end

  # 1文字を飛ばして同じ文字のチェック
  if i+2 < len && s[i] == s[i+2]
    puts "#{i+1} #{i+3}"
    found = true
    break
  end
end

# アンバランスな部分文字列が見つからなかった場合
puts "-1 -1" unless found