레이팅 미적용Just Odd Inventions 社は,「ただ奇妙な発明(just odd inventions)」をすることで知られている会社である.
ここでは略してJOI 社と呼ぶ.
JOI 社は,看板商品である「長いだけのネクタイ」発売5 周年を記念し,新しく「長くなるだけのネクタ
イ」を開発した.この新型ネクタイの特徴は,その名の通り長さをいくらでも伸ばせることである.
JOI 社は,新型ネクタイの宣伝を目的とした披露会の開催を決定し,その司会にあなたを抜擢した.披露
会ではまず,新型ネクタイを着用した何人かのモデルが舞台上に登壇する.最初,各モデルが着用している
ネクタイの長さはすべて1 である.
その後,あなたはネクタイの長さを伸ばせる機能を観客に実感してもらうためのパフォーマンスをN 回
行う.各パフォーマンスは以下のように行われる.
1. まず,観客に好きな数を1 つ唱えてもらう.ここで観客が唱えた数をx とおく.
2. 次に,司会のあなたはこれに反応するか無視するかを選ぶ.
• 反応することを選んだ場合,あなたは登壇しているモデルのうち着用しているネクタイの長さが
x 以下であるような者を1 人選び,そのモデルのネクタイの長さをx にする(着用しているネク
タイの長さが元々x であるようなモデルも選ぶことができる点に注意せよ).ただし,選ぶこと
のできるモデルが1 人も存在しない場合,披露会は失敗に終わる.
• 無視することを選んだ場合,何もしない.
ただし,観客の唱えた数を2 回以上連続で無視してしまうと,観客が機嫌を損ね,披露会は失敗に終わる.
舞台上に登壇させるモデルの人数k (k ≧1) はまだ決まっていないが,モデルを雇うのにはお金がかかる
ため,k の値はできるだけ小さい方が望ましい.披露会が失敗に終わらないために必要なモデルの人数は
各パフォーマンスで観客が唱える数に依存するが,あなたはその予知能力により,i 回目(1 ≦i ≦N) のパ
フォーマンスで観客が唱える数がAi であることを予見した.
披露会で観客が唱える数の情報が与えられたとき,披露会が失敗に終わらないために必要なモデルの人数
k の最小値を求めるプログラムを作成せよ.
第24 回日本情報オリンピック(JOI 2024/2025) 本選
2025 年2 月2 日(オンライン開催)
• 2 ≦N ≦5 000 000.
• 1 ≦Ai ≦21 (1 ≦i ≦N).
• 入力される値はすべて整数である.
- (10 点) N ≦15.
- (6 点) N ≦500,Ai ≦2 (1 ≦i ≦N).
- (12 点) N ≦500,Ai ≦5 (1 ≦i ≦N).
- (18 点) N ≦500,Ai ≦15 (1 ≦i ≦N).
- (26 点) N ≦500 000,Ai ≦15 (1 ≦i ≦N).
- (10 点) N ≦500 000.
- (18 点) 追加の制約はない.
第24 回日本情報オリンピック(JOI 2024/2025) 本選
2025 年2 月2 日(オンライン開催)
入力は以下の形式で標準入力から与えられる.
N
A1 A2 · · · AN
標準出力に,披露会が失敗に終わらないために必要なモデルの人数k の最小値を1 行で出力せよ.
5
5 3 4 2 1
2
6
2 1 1 2 2 1
1
10
2 4 6 7 4 5 5 3 4 1
3