JOI2014春合宿 H - JOIOJI - かんプリンの学習記録

問題概要
思考の流れ
提出プログラム
感想

問題概要

長さ ${1\le N\le 2×10^5}$ のJ,O,Iからなる文字列 ${S}$ が与えられる. ${S}$ の連続する部分文字列であり, 以下の条件を満たすものの中で最長の文字列を求めよ.

文字列に含まれるJ,O,Iの数が等しい.

思考の流れ

区間に含まれる2つの文字の個数が等しい問題は「累積和をして式変形」を用いることで答えることができる.
今回の問題は3つの文字の個数が等しい場合である.

${\downarrow}$

区間 ${[0,i)}$ に含まれるそれぞれの文字の数を ${J[i],O[i],I[i]}$ とすると区間 ${[i,j)}$ に含まれる3つの文字の数が等しいという条件は ${J[j]-J[i]=O[j]-O[i]=I[j]-I[i]}$ と表すことができる.

${\downarrow}$

式変形すると ${J[j]-O[j]=J[i]-O[i], J[j]-I[j]=J[i]-I[i]}$ となる.
${JO[i]=J[i]-O[i], JI[j]=J[j]-I[j]}$ とすると, ${JO[x]=JO[y]かつJI[x]=JI[y]}$ となるような ${x,y}$ の組の数が答えとなる.

${\downarrow}$

各 ${x}$ に対して ${JO[x]とJI[x]とx}$ をタプルとして持ち, 昇順ソートすると, ${JOとJI}$ が等しいものが並ぶ. そうして前から見ていくことで最長のものを探すことができる.

提出プログラム

未提出

感想

思考の流れの最後の矢印が思い浮かばなかった.

kanpurin.hatenablog.com