![]() |
|
2007年12月16日
情報オリンピック日本委員会
|
文字列を扱うきわめて基本的な問題である.この問題は2番ということもありプログラミングの基本を問う問題となっている.
まずは問題文をよく読み,入力が最大10000文字の文字列であることを確認する.10000文字の文字列の扱いは,使用するプログラミング言語により,
・一つの変数に文字列として記憶
・10000要素の配列を用意し,1文字ずつばらして記憶
または
・1文字ずつ入力から読み込みながら処理(文字列の各文字に対してランダムアクセスが必要ない場合)
のいずれかになるだろう.この問題の場合には,上記のどの方法を取っても問題はない.
この問題では,与えられた文字列の中に含まれている JOI と IOI の個数を数え上げるだけなので,文字列の先頭より1文字ずつずらしながら連続する3文字をチェックしていき,それぞれの出現数をカウントしていくだけで十分である.1文字ずつ読み込みながら処理する場合には,直前に読み込んだ2文字を記憶しておくだけで事足りる.
どのような方法をとるにせよ,入力文字数を n とすると n に比例した時間 O(n) だけで処理できるだろう.
また,採点用データセットの5つの入力データは以下の方針に従いランダムに生成された文字列を使用した.
1:JOIのみ 長さ180+JOI(10%)
2:IOIのみ 長さ180+IOI(10%)
3:JOI,IOI混合、長さ180+JOI(5%)+IOI(5%)
4:混合IOIOIを含む長さ1000+JOI(5%)+IOI(5%)+IOIOI(1%)
5:混合JOIOIも含む長さ5000+JOI(5%)+IOI(5%)+IOIOI(1%)+JOIOI(1%)
特にデータ4と5では,1000文字を超す長い文字列に対応できなかったと思われる者や,この2つにのみ含まれているIOIOIやJOIOIを正しく扱えていない者が一部見受けられたが,この2つのパターンは問題文の入出力データ例にも含まれていたので注意が必要だっただろう.