本文、提出履歴、提出フォームを準備しています。
すべての値から を引き、初期値を として考える。 ならすべての値に を施せばよいので、以降は と仮定する。
、、、、 とおく。最終値は必ず全体の平均 である。何回操作しても、各値を既約分数で表したときの分母は の冪なので、 が の冪でなければ不可能である。
が の冪であるとする。 なので である。 とおくと、最小操作回数は である。
Construction
なら は奇数である。大きさ のグループを 個作り、各グループの の個数をそれぞれ とする。残りを大きさ のグループ 個に分ける。
Bound
一度でも同じ操作で選ばれた 2 つの添字の間に辺を張ってグラフ を作り、連結成分数を とする。ある連結成分の大きさが なら、その成分の最終的な総和 は整数でなければならないので、 は の倍数である。各連結成分の大きさを と書くと、 である。
全体の時間計算量は である。
Solution written by GPT5.6
大きさ のグループに が 個含まれるなら、 の個数はそれぞれ 、、 でなければならない。したがって であり、すべての大きさ のグループで の和を にすればよい。 の定義より常に可能である。
各グループはちょうど「グループの大きさから を引いた回数」の操作で平均化できる。大きさ のグループは からなり総和が奇数である。大きさ のグループは、すべての値を で割ると総和が奇数の グループになる。
大きさ 、要素が 、総和が奇数 のグループを考える。操作を逆向きに構成する。最初は最終平均 が 個あると考える。同じ値 を 2 個選び、一方を元の整数 として確定し、もう一方を に戻せば、平均操作 1 回を逆向きに復元できる。
現在の有効な要素数が のとき、 とする。すべての有効な値の小数部分は なので、値は と の 2 種類しか現れない。高い方の値の個数を とし、同じ種類同士を 2 個ずつ組にする。
次の段階の有効な要素数は である。各状態 について、今後復元可能な未復元の の個数は 1 つの整数区間を成す。 では または であり、上の遷移から小さい 順に区間を計算できる。接頭・接尾の最小値と最大値を使えば 1 レベルを で処理でき、全レベルの大きさの和も である。復元時には次の状態が可能な区間に残る遷移を 1 つ選ぶ。記録した逆操作を逆順にすれば 回の正方向の操作が得られる。
番目の連結成分に初めから含まれる の個数を とする。その総和は なので である。 は奇数なので、
したがって である。大きさ の連結成分を作るには少なくとも 回の操作が必要なので、操作回数全体は少なくとも
である。
