数日掛けても全く解けなかった、提出コードも嘘っぽいものしかなくて、想定解っぽいものを得るために片っ端から読む必要があった

解法は知るとそんなに難しくないのだが、なんか異常に難しい。

問題概要

Dashboard - 2014-2015 ACM-ICPC, Asia Mudanjiang Regional Contest - Codeforces

長さNの文字列Sが与えられる。ただし文字の種類はN種類あることもある(各文字はcharではなくintで表される)

全ての部分文字列について、ABBA型となるか判定する。ただし、A or Bは空文字列でもよい。

N <= 5000

解法

ABB | A ←この縦棒を固定する。

| ABB | A ←そのつぎに左端を動かして調べていく

この固定方法のキモは、Aとしてありえる文字列長が区間となること。

追記

嘘です。まともな解法ないのでは？