🐕

125. 一次変換

2023/03/22に公開

【問題概要】
正整数 N が与えられます。数直線上に、N 個の点 x1, x2, ..., xn があります。この数直線上において、あなたは、以下の 3 種類の操作を 0 回以上任意の順序で行うことができます。

・操作 1: 任意の 2 点 x, y (x≠y) を選び、座標値の平均 (x+y)/2 に新たな点を置く。
・操作 2: 任意の 2 点 x, y (x<y) を選び、座標値を (y-x)/3 倍して整数に丸めた座標に新たな点を置く。
・操作 3: 任意の 1 点 x を選び、座標値を反転した座標に新たな点を置く。

操作を行った後にあなたが置ける点の最大値を求めてください。

【解説】
この問題は、与えられた N 個の点に対して、一次変換という操作を繰り返し行うことで、新たな点を生成する問題となっています。具体的には、操作 1 で平均座標に新たな点を置き、操作 2 で座標値を変換して新たな点を置き、操作 3 で座標値を反転させて新たな点を置くことができます。

この問題では、与えられた点の座標値を昇順にソートし、一次変換を繰り返し行いながら、新たに生成される点をリストに格納していきます。一次変換を行う際には、操作 1 から順に試していき、新たに生成された点の座標値がすでにリストに含まれている場合は、それ以上操作を行わずに次の点に移ります。また、操作 2 で座標値を変換する場合は、生成される新たな点の座標値が整数であるかどうかを判定し、整数である場合のみ新たな点をリストに格納します。

以上のように、与えられた N 個の点に対して、一次変換を繰り返し行いながら新たな点を生成することで、置ける点の最大値を求めることができます。

【関連する問題】
Atcoderの「Rounding」問題が、本問題と関連しています。
「Rounding」

レーティング難易度(★): 1700
ACした回答者に絞った場合のレーティング帯の範囲(数値): 1181 - 2325
レーティング難易度(%): 70.5%
レーティング(数値): 1859
AC率(%): 12.2%
ACしたスコアの高い回答者: https://atcoder.jp/users/chinax
解説ブログ: https://atcoder.jp/contests/abc198/editorial/1532