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

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

解説

解説担当：山縣龍人

この問題は，各 i = 1, 2, …, N に対し，|A₁ - A_i|, |A₂ - A_i|, …, |A_N - A_i| のうちの最大値を出力する問題である．

小課題 1

小課題 1 では N = 2 であった．したがって，|A₁ - A₂| を 2 回出力すれば良い．

小課題 2

各 i = 1, 2, …, N に対し，|A₁ - A_i|, |A₂ - A_i|, …, |A_N - A_i| の値を全て計算し，その最大値を出力することを考える．

小課題 2 では N ≦ 1000 であるから，時間計算量 O(N²) のこのアルゴリズムは十分高速である．

小課題 3

小課題 2 では N ≦ 250000 であるから，|A₁ - A_i|, |A₂ - A_i|, …, |A_N - A_i| の値を全て計算することは時間制限に間に合わない．

数直線上の A₁, A₂, …, A_N の位置に点を打つことを考える．すると，ある人との年齢の差の最大値は，ある点から最も遠い点までの距離と解釈することができる．

点 A_i から最も遠い点は，点 A_i から数直線上の正の方向に最も遠い点か，点 A_i から数直線上の負の方向に最も遠い点のどちらかである．ここで，点 A_i から数直線上の (正 or 負) の方向に最も遠い点は，それぞれ A₁, A₂, …, A_N のうちの最大値と最小値に対応する．

したがって，mn = min { A₁, A₂, …, A_N }，mx = max { A₁, A₂, …, A_N } とすれば，max { mx - A_i, A_i - mn } が点 A_i から最も遠い点までの距離となる．

以上をまとめると，mn = min { A₁, A₂, …, A_N }，mx = max { A₁, A₂, …, A_N } をあらかじめ計算し，各 i = 1, 2, …, N に対して max { mx - A_i, A_i - mn } を出力すれば良い．

このアルゴリズムは O(N) 時間で動作するから，十分高速である．