No.111 あばばばば

Quiz

https://yukicoder.me/problems/no/111

Submit

https://yukicoder.me/submissions/336368

解法

  • まず、aから始まる回文の数を考える
  • サンプル2の場合
ababababa
  • abaは4つ
  • ababaは3つ
  • abababaは2つ
  • ababababaは1つ
  • 取れる。
  • 一般に1+2+3+...+Nとなりそう
  • ここでNは、abaの場合を考えて(L-3) / 2 + 1
  • となる。
    • L-3 : 残りの長さ
    • 2 : 2ずつずらしながら数える
    • +1 : 1番最初の分
  • 1+2+3+...+Nの和は等差数列の和なので求まる
  • これでabaの場合は求まった
  • 文字列から最初と最後のaを取り除くと
bababab
  • これはL-2として同様に数えられる
  • よってO(1)で解くことができました