いよいよ待ちに待った「国際情報オリンピック日本代表プログラミングコンテスト」(IJPC : IOIer Japan Programming Contest)の開催だ。2010年にカナダ、2011年にタイで開催された国際情報オリンピック(IOI)に日本代表として出場した 計 5 人が問題を作るプログラミングコンテストであり、5 時間で 3 問の問題を解くという IOI に似た形式である。

IJPC の参加者への感謝の意を表するとともに、IJPC を盛り上げるために巨大な垂れ幕を作ろう。出来るだけ大きく目立つものにしたいところではあるが、あまり垂れ幕作りに時間をかけすぎると肝心の大会問題の準備時間を削ってしまうことになる。つまり、手間を省きつつ大きな垂れ幕を作りたい。

ところで手元には都合のよいことに、何に使われたのかわからない巨大な垂れ幕がある。この垂れ幕は非常に長く、もとから何かの文字列が書かれている。このままでは当然 IJPC 用の垂れ幕として使うことはできないが、少しだけ修正してこれを IJPC 用に使えないだろうか?

もとから書かれている文字列に "IJPC" という文字列が含まれていればうれしいのだが、さすがにそう都合よくはいかないだろう。ある程度の文字を書き換える必要があるはずだが、文字を書き換える作業は垂れ幕が大きいこともありとても時間がかかる。さて、ここでプログラムの出番だ。できるだけ少ない書き換え回数でこの垂れ幕を使えるようにする方法を求めよう。

英大文字からなる N 文字の文字列 S がある。S のある位置の文字を別の文字に書き換える操作を繰り返し、S の部分文字列に "IJPC" という 4 文字が現れるようにしたい。ここである文字列から 0 文字以上の任意の文字を削除して得られるような文字列を、元の文字列の部分文字列と呼ぶ。

次のパラメータをもつプロシージャ replace(N, S) を実装せよ:

• N -- 与えられる文字列の文字数。N ≧ 4 を仮定してよい。
• S -- 英大文字からなる文字列。S は N 文字であると仮定してよい。

replace(N, S) は S の部分文字列に "IJPC" が現れるようにするために必要な最小の書き換え回数を戻り値として返す必要がある。

N = 8, S = "IAMJAPLJ" の場合を考える。

この場合、S の 7 文字目または 8 文字目のどちらかを文字 'C' に書き換えることで S の部分文字列に "IJPC" が現れるようにすることができる。したがって replace(N, S) は 1 を返す必要がある。

N = 28, S = "IOIERJAPANPROGRAMMINGCONTEST" の場合を考える。

この場合 S はもとから "IJPC" を部分文字列として含んでいるため、書き換えを行う必要はない。したがって replace(N, S) は 0 を返す必要がある。