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



可复制的 PDF 提取文本
The 20th Japanese Olympiad in Informatics (JOI 2020/2021)
JOI Open Contest
June 6, 2021
financial
決算報告(Financial Report)
JOI マートはN 日間の歴史を持つ商店である.JOI マートにおいて,開業からi 日目(1 ≦i ≦N) の売上
はAi 円であった.
今日,JOI マートの店長であるビ太郎は,決算報告でプレゼンテーションをすることになった.プレゼン
テーションでは,いくつかの日を選んだときの売上を時系列順に並べた棒グラフを用いて業績の変化を見せ
る.ここで,彼は印象がよくなるように見せるデータを選び,売上の伸びをアピールしようと考えた.
ここで,ビ太郎がm 日分(1 ≦m ≦N) のデータを選び,これが開業からp1, p2, . . . , pm 日目(1 ≦p1 <
p2 < · · · < pm ≦N) のデータであったとき,棒グラフの印象点は以下のように定められる.
選ばれたデータだけを見たときに,それまでの売上の最高記録を更新する回数.すなわち,j = 1 ま
たはmax{Ap1, Ap2, . . . , Apj−1} < Ap j となるj (1 ≦j ≦m) の個数.
ビ太郎は印象点をできるだけ大きくしたいが,データの選び方によってはプレゼンテーションが不自然に
見えてしまう.そのため,以下の条件を両方とも満たすようにデータを選ぶことにした.
• 最新の売上のデータを見せる.すなわち,pm = N である.
• どの連続する2 つのデータもD 日以内しか離れていない.すなわち,m ≧2 のとき,どのj
(1 ≦j ≦m −1) についてもpj+1 −p j ≦D である.
開業時から現在までのJOI マートの売上のデータと,整数D が与えられたとき,プレゼンテーションで
見せる棒グラフの印象点の最大値を求めるプログラムを作成せよ.
入力
入力は以下の形式で標準入力から与えられる.入力される値はすべて整数である.
N D
A1 · · · AN
出力
標準出力に,プレゼンテーションで見せる棒グラフの印象点の最大値を1 行で出力せよ.
決算報告– 1 / 3
The 20th Japanese Olympiad in Informatics (JOI 2020/2021)
JOI Open Contest
June 6, 2021
financial
制約
• 1 ≦N ≦300 000.
• 1 ≦D ≦N.
• 0 ≦Ai ≦1 000 000 000 (1 ≦i ≦N).
小課題
1. (14 点) N ≦20.
2. (14 点) N ≦400.
3. (20 点) N ≦7 000.
4. (12 点) D = 1.
5. (5 点) D = N.
6. (35 点) 追加の制約はない.
入出力例
入力例1 出力例1
7 1 3
100 600 600 200 300 500 500
この入力例では,問題文中の条件を満たす棒グラフとして,以下の7 通りが考えられる.
• 開業から1, 2, 3, 4, 5, 6, 7 日目のデータを選んだ棒グラフを見せる.このときの印象点は2 点である.
• 開業から2, 3, 4, 5, 6, 7 日目のデータを選んだ棒グラフを見せる.このときの印象点は1 点である.
• 開業から3, 4, 5, 6, 7 日目のデータを選んだ棒グラフを見せる.このときの印象点は1 点である.
• 開業から4, 5, 6, 7 日目のデータを選んだ棒グラフを見せる.このときの印象点は3 点である.
• 開業から5, 6, 7 日目のデータを選んだ棒グラフを見せる.このときの印象点は2 点である.
• 開業から6, 7 日目のデータを選んだ棒グラフを見せる.このときの印象点は1 点である.
• 開業から7 日目のデータを選んだ棒グラフを見せる.このときの印象点は1 点である.
これより,印象点を最大で3 点にできるため,プログラムが3 を出力すると正解となる.
この入力例は小課題1, 2, 3, 4, 6 の制約を満たす.
決算報告– 2 / 3
The 20th Japanese Olympiad in Informatics (JOI 2020/2021)
JOI Open Contest
June 6, 2021
financial
入力例2 出力例2
6 6 4
100 500 200 400 600 300
この入力例では,開業から1, 3, 4, 5, 6 日目のデータを見せた棒グラフが,印象点を最も高くする.このと
き選ばれた売上のデータは,順に100, 200, 400, 600, 300 円となっており,売上の最高記録を4 回更新する
ことになるため,印象点は4 点となる.よって4 を出力する.
この入力例は小課題1, 2, 3, 5, 6 の制約を満たす.
入力例3 出力例3
11 2 4
1 4 4 2 2 4 9 5 7 0 3
この入力例では,例えば開業から1, 3, 5, 6, 8, 9, 11 日目のデータを見せた棒グラフが,印象点を最も高く
する.このとき選ばれた売上のデータは,順に1, 4, 2, 4, 5, 7, 3 円となっており,売上の最高記録を4 回更新
することになるため,印象点は4 点となる.よって4 を出力する.なお,問題文中の条件を満たしたうえで
印象点を4 点にする棒グラフは,他にも複数考えられる.
この入力例は小課題1, 2, 3, 6 の制約を満たす.
決算報告– 3 / 3