AtCoder Grand Contest 016 A: Shrinking
アルファベット小文字からなる文字列がs[i]で与えられる。新しい文字列のi番目の文字をs[i] or s[i + 1] のいずれかを選んで構成する、という作業を行う。この作業を何回か繰り返して全ての文字が単一のアルファベットで構成されるようにしたい。最短回数を求めよ。
Nが最大100までであり、一回の作業でN文字がN-1文字になる。よって最後の一文字に慣れば必ず単一のアルファベットになるため、文字を固定してしまえばO(N^2)でシミュレーションできる。最短回数は貪欲に目的のアルファベットにしてしまえばよい。アルファベットの数をAとするとO(AN^2)。
