第25回日本情報オリンピック　二次予選

2025年12月15日
情報オリンピック日本委員会

問題文

J, O, I からなる長さ N の文字列 S がある． JOI 君は文字列 S に対して，以下の操作をそれ以上操作が行えなくなるまで繰り返す．

• S の中で J, O, I がこの順で連続して並んでいる箇所を 1 つ選び，その部分を O, I, J の並びに置き換える．

操作の繰り返しは必ず終了し，また操作の方法によらず最終的な文字列の状態が一意に定まることが証明できる．

はじめの文字列 S の情報が与えられたとき，最終的な文字列 S を求めるプログラムを作成せよ．

制約

• 3 ≦ N ≦ 500 000．
• S は J, O, I からなる長さ N の文字列である．
• N は整数である．

小課題

1. (14 点) N ≦ 100．
2. (27 点) N は 3 の倍数で， S は JOI を N / 3 回繰り返したものである．
3. (29 点) ある整数 k (2 ≦ k ≦ N) が存在して， S の 1 文字目から k 文字目まではすべて J であり，一方 k + 1 文字目以降は J でない．
4. (30 点) 追加の制約はない．

入力

入力は以下の形式で与えられる．
N
S

出力

最終的な文字列 S を 1 行で出力せよ．

入出力例

入力例 1
6
JOIJOI

出力例 1
OIOIJJ

例えば，以下のように JOI 君が操作を行うことが考えられる．

最初，S = JOIJOI である．

1. 1 文字目から 3 文字目に対して操作を行う． S = OIJJOI となる．
2. 4 文字目から 6 文字目に対して操作を行う． S = OIJOIJ となる．
3. 3 文字目から 5 文字目に対して操作を行う． S = OIOIJJ となる．

これ以上操作を行うことはできないため，OIOIJJ を出力する．

この入力例は小課題 1,2,4 の制約を満たす．

入力例 2
8
JJJOIOIO

出力例 2
OIOIJJJO

この入力例は小課題 1,3,4 の制約を満たす．

入力例 3
20
JJOIJOIJOOIJOIIJJOIO

出力例 3
OIOIJJJJOOIOIJIOIJJO

この入力例は小課題 1,4 の制約を満たす．