以下页面来自日本信息收集官方发布的原题PDF,已完整保存并渲染到本地。

可复制的 PDF 提取文本
Stamps: 判子(はんこ)
input ファイル“stamps.in”
output 標準出力
ソースファイルstamps.c/stamps.cpp
時間制限1 秒/ データ
IOI 国にある老舗判子メーカーのIOI 堂は今年で創業101 年となる.これを記念しIOI 堂では
オーダーメードで長いメッセージを入れた判子を作るサービスを始めることにした.というの
も昨年,IOI 堂は手動で判子の特定の部分に文字を挿入したり,抜き出したり,入れ替えたりす
ることができる判子を開発し,より長い文字列の判子を作ることを可能としたのである.
今回作る判子は,アルファベットのI とO の2 文字のみから構成されるIOI 語を対象にす
る.また,既存の機械で予め適当な1 文字以上の長さの判子を作り,その文字列を適宜編集し
て注文のメッセージを作ることにする.ただし,古くからの仕様により,この機械で作ること
ができるのは,I で始まりI で終わる,どの連続した2 文字も同一ではない文字列(例えばI や
IOI やIOIO…OIOI) の判子である.
現在,IOI 堂では人手が足りていないので作業時間をできる限り短くしたい.機械作業は時間
がかからないが,その後の3種類の編集作業,すなわち1 つの文字を挿入する作業,1 つの文字を
削除する作業,1 つの文字を入れ替える作業は,各々1 回あたり1 秒の時間が必要である.例えば
IOIOIOI という文字列の判子を機械で作った後に,3 文字目をO に入れ替え,5 文字目と6 文字
目の間にO を1 文字挿入しIOOOIOOI という文字列の判子を作ると2 秒の時間が必要となる.
そこで,注文のメッセージが与えられた時,最短の作業時間と,最短時間で作業した時に予
め機械で作らなければならない判子の長さの最小値を求めるプログラムを書いてほしい.
Input. 入力ファイルstamps.in の1 行目には,1 つの注文されたメッセージの長さを表す整
数N(1 ≦N ≦1000000) が書かれている.2 行目には注文されたメッセージを表すN 文字のI
またはO からなる文字列S が書かれている.
Output. 出力は標準出力に行うこと.出力の1 行目には最短の作業時間を書け.2 行目には最
短時間で作業した時に予め機械で作らなければならない判子の長さの最小値を書け.
採点基準採点用データのうち,配点の40% 分についてはN ≦5000 を満たす.
例1 例2 例3
stamps.in 標準出力 stamps.in 標準出力 stamps.in 標準出力
8 2 5 0 5 2
IOOOIOOI 7 IOIOI 5 IIIII 5
判子–1/1