問題
考察
数列の最大値と最小値の差を1以下にするために最低限必要となる操作の回数を求めてくださいという問題です。
結論
結論としては、下記の手続きに沿ったコードを作成すればACできます。
- 次の2つの値を求める。
- 数列$A$の平均値。小数切り捨て。(${Ave}_1$とする。)
- 数列$A$の平均値。小数切り上げ。(${Ave}_2$とする。)
- 次の2つの値を求める。
- 数列$A$で、「${Ave}_1$より小さい値」に該当する各項の「${Ave}_1$との差の絶対値」を合計した値。($d_1$とする。)
- 数列$A$で、「${Ave}_2$より大きい値」に該当する各項の「${Ave}_2$との差の絶対値」を合計した値。($d_2$とする。)
- $d_1$と$d_2$のうち、より大きい値が答え。
なぜACできるかを説明していきます。
数列の各項の値は何になるか
数列の最大値と最小値の差を1以下にするとき、数列の各項の値は何になるかを考えます。まず、今回の問題で行う操作では、1つの項の値を1増やし、1つの項の値を1減らします。この操作で、各項の和が変わることはありません。そのため、数列の各項の最終的な値は各項の和を項数で割った値、すなわち平均値の近くになりそうです。
平均値は、小数を含む可能性があります。しかし、今回の問題では最大値と最小値の差を1にすればいいです。そのため、各項の値は「平均値の小数を切り捨てた値(${Ave}_1$)」か「平均値の小数を切り上げた値(${Ave}_2$)」のどちらかとなります。各項が平均値の小数を切り捨てた値(${Ave}_1$)」か「平均値の小数を切り上げた値(${Ave}_2$)」のどちらかなった形を「理想形」ということにします。
操作の対象となる2項を選び方を考える。
数列の各項の値が「平均値の小数を切り捨てた値(${Ave}_1$)」か「平均値の小数を切り上げた値(${Ave}_2$)」になるはずということが分かりました。あとは理想形になるのに必要な操作の回数を調べていきます。そのために操作対象となる2つの項は毎回どれを選べば良いかを考えます。通常、${Ave}_1 ≦ {Ave}_2$ですから、数列の各項に対して下記の事実があることは分かるかと思います。
- ${Ave}_1$より小さい値→$({Ave}_1との差の絶対値) ≦ ({Ave}_2との差の絶対値)$
- ${Ave}_2$より大きい値→$({Ave}_1との差の絶対値) ≧ ({Ave}_2との差の絶対値)$
上記の事実から、${Ave}_1$より小さい値は${Ave}_1$になるように、${Ave}_2$より大きい値は${Ave}_2$になるように操作対象を選んでいけば少ない回数で理想形になります。
この事実を踏まえた上で、操作対象となる2つの項の選び方を考えます。
case1. 数列に「Ave1より小さい値」の項と「Ave2より大きい値」の項の両方が存在する場合
この場合、「${Ave}_1$より小さい値」の項と「${Ave}_2$より大きい値」の項を選べば理想形に近づいていきます。
case2. 数列に「Ave1より小さい値」の項が存在するが、「Ave2より大きい値」の項が存在しない場合
この場合、一方は「${Ave}_1$より小さい値」の項を選べば良いことは分かるかと思います。もう一方は数列内に既に存在している、「値が${Ave}_2$」の項を選べば良いです。近づけるのは平均値ですから、Ave1より小さい値」の項が存在するが、「Ave2より大きい値」の項が存在しない状況では、「値が${Ave}_2$」の項は確実に存在するといえるためです。
case3. 数列に「Ave2より大きい値」の項が存在するが、「Ave1より小さい値」の項が存在しない場合
この場合、一方は「${Ave}_2$より大きい値」の項。もう一方は数列内に既に存在している、「値が${Ave}_1$」の項を選べば良いです。先程と同様の理由で、この条件を満たす場合は「値が${Ave}_1$」の項は確実に存在するといえます。
以上のことから、操作対象となる2つの項は毎回どれを選べばいいか分かりました。
操作回数は何回になるか
先程のcase1～3から、次のような考え方で操作を繰り返すことになります。
-
最初は「Ave1より小さい値」の項と「Ave2より大きい値」の項の両方が存在する
- case1に該当する。そこで、「Ave1より小さい値」の項と「Ave2より大きい値」の項を選んでどちらかが存在しなくなるまでcase1の操作を繰り返す。
-
「Ave1より小さい値」の項と「Ave2より大きい値」の項のどちらかが存在しなくなった
- case2かcase3のどちらかに該当するため、理想形になるまで該当するcaseの操作を繰り返す。
あとは操作回数を求めていくわけですが、1つめの操作回数は『「${Ave}_1$より小さい値」に該当する各項と「${Ave}_1$との差の絶対値」の合計値』と『${Ave}_2$より大きい値」に該当する各項と「${Ave}_2$との差の絶対値」の合計値』のうちの小さい方になります。そして2つめの操作回数は、先程の値の大きい方の値から、小さい方の値を引いた回数になります。結局のところ、必要な回数は2つの値のうちの大きい方を求めれば良いとことになります。
これで、計算用$O(N)$と、十分に間に合う時間で求めることができます。
提出コード(コンテスト後)
ご不明点などがあれば教えていただけると幸いです。