スタンプラリー２(16本選2)

N個の店があり、それぞれJかOかIが決まっている。3店を選んでJOIを作る。

なお、3店は番号の小さい順に選ぶ必要がある。

ここで、任意の場所に任意の文字の店を一つ追加して、JOIを作る通り数を最大化したいという問題。

まず、最初の段階でJOIの通り数を数える。数える方法は、Oの店を見つけたらその前後のJとIの数をかけ、総和を求める。(あらかじめJ,O,Iそれぞれに関して累積和を求めておく。)

また、Jを追加する際は、一番番号の小さい場所に追加すべきだし、Iは一番番号の大きい場所に追加すべきである。

Oは全通り試すほかないので愚直に試す。

O(N)で求められる。

難易度は6程度に感じられた

http://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=2315663#1