DOJ logoDOJ
問題
最近追加された問題保存した問題Workbooks
カテゴリDLCコンテストグループチーム掲示板
ランキング
正解数ランキングストリークランキングDOJ Powerランキング
提出状況
問題募集ログイン新規登録
DOJ logoDOJ

OI形式のサブタスク採点、Eloレーティング、Discord連携を備えたオンラインジャッジです。

問題
問題一覧カテゴリ
コミュニティ
コンテストランキング掲示板お知らせ外部のコンテストを開催するガイド
アカウント
ログイン新規登録ジャッジ状態
ポリシー
利用規約DLCの利用規則プライバシーAPI 文書言語ランタイムコンテストの順位報酬レーティングとパフォーマンス
© 2026 DOJ
All rights reserved
解説

いち に さん 2

問題に戻る

解説

すべての値から 111 を引き、初期値を 0,1,20,1,20,1,2 として考える。A<CA<CA<C ならすべての値に x↦2−xx\mapsto 2-xx↦2−x を施せばよいので、以降は A≥CA\ge CA≥C と仮定する。

N=A+B+CN=A+B+CN=A+B+C、S=B+2CS=B+2CS=B+2C、g=gcd⁡(N,S、、 とおく。最終値は必ず全体の平均 である。何回操作しても、各値を既約分数で表したときの分母は の冪なので、 が の冪でなければ不可能である。

ppp が 222 の冪であるとする。A≥CA\ge CA≥C なので q≤pq\le pq≤p である。λ=max⁡(0,C−g⌊ とおくと、最小操作回数は である。

Construction

p>1p>1p>1 なら qqq は奇数である。大きさ 2p2p2p のグループを λ\lambdaλ 個作り、各グループの 0,1,20,1,20 の個数をそれぞれ とする。残りを大きさ のグループ 個に分ける。

Bound

一度でも同じ操作で選ばれた 2 つの添字の間に辺を張ってグラフ GGG を作り、連結成分数を kkk とする。ある連結成分の大きさが sss なら、その成分の最終的な総和 sq/psq/psq/p は整数でなければならないので、sss は pp の倍数である。各連結成分の大きさを と書くと、 である。

全体の時間計算量は O(N)O(N)O(N) である。

Solution written by GPT5.6

)g=\gcd(N,S)
g=gcd(N,S)
p=Ngp=\dfrac Ngp=gN​
q=Sgq=\dfrac Sgq=gS​
q/pq/pq/p
222
ppp
222
q2⌋)\lambda=\max\left(0,C-g\left\lfloor\dfrac q2\right\rfloor\right)
λ=max(0,C−g⌊2q​⌋)
N−g+λN-g+\lambdaN−g+λ
,
1
,
2
2p−q,0,q2p-q,0,q2p−q,0,q
ppp
g−2λg-2\lambdag−2λ

大きさ ppp のグループに 222 が ccc 個含まれるなら、0,1,20,1,20,1,2 の個数はそれぞれ p−q+cp-q+cp−q+c、q−2cq-2cq−2c、ccc でなければならない。したがって 0≤c≤⌊q/2⌋0\le c\le\lfloor q/2\rfloor0≤c≤⌊q/2⌋ であり、すべての大きさ ppp のグループで ccc の和を C−λqC-\lambda qC−λq にすればよい。λ\lambdaλ の定義より常に可能である。

各グループはちょうど「グループの大きさから 111 を引いた回数」の操作で平均化できる。大きさ ppp のグループは 0,1,20,1,20,1,2 からなり総和が奇数である。大きさ 2p2p2p のグループは、すべての値を 222 で割ると総和が奇数の 0,10,10,1 グループになる。

大きさ D=2kD=2^kD=2k、要素が 0,1,20,1,20,1,2、総和が奇数 qqq のグループを考える。操作を逆向きに構成する。最初は最終平均 q/Dq/Dq/D が DDD 個あると考える。同じ値 xxx を 2 個選び、一方を元の整数 a∈{0,1,2}a\in\{0,1,2\}a∈{0,1,2} として確定し、もう一方を 2x−a2x-a2x−a に戻せば、平均操作 1 回を逆向きに復元できる。

現在の有効な要素数が DDD のとき、r=q mod Dr=q\bmod Dr=qmodD とする。すべての有効な値の小数部分は r/Dr/Dr/D なので、値は r/Dr/Dr/D と 1+r/D1+r/D1+r/D の 2 種類しか現れない。高い方の値の個数を HHH とし、同じ種類同士を 2 個ずつ組にする。

  • r<D/2r<D/2r<D/2 なら、低い値の組は 000 を 1 個復元して低い値を 1 個残す。高い値の組は 111 を復元して高い値を残すか、222 を復元して低い値を残せる。
  • r>D/2r>D/2r>D/2 なら、高い値の組は 222 を 1 個復元して高い値を 1 個残す。低い値の組は 111 を復元して低い値を残すか、000 を復元して高い値を残せる。

次の段階の有効な要素数は D/2D/2D/2 である。各状態 (D,H)(D,H)(D,H) について、今後復元可能な未復元の 222 の個数は 1 つの整数区間を成す。D=2D=2D=2 では (H,c)=(0,0)(H,c)=(0,0)(H,c)=(0,0) または (2,1)(2,1)(2,1) であり、上の遷移から小さい DDD 順に区間を計算できる。接頭・接尾の最小値と最大値を使えば 1 レベルを O(D)O(D)O(D) で処理でき、全レベルの大きさの和も O(D)O(D)O(D) である。復元時には次の状態が可能な区間に残る遷移を 1 つ選ぶ。記録した逆操作を逆順にすれば D−1D-1D−1 回の正方向の操作が得られる。

p
ps1,ps2,…,pskps_1,ps_2,\ldots,ps_kps1​,ps2​,…,psk​
s1+s2+⋯+sk=gs_1+s_2+\cdots+s_k=gs1​+s2​+⋯+sk​=g

iii 番目の連結成分に初めから含まれる 222 の個数を cic_ici​ とする。その総和は qsiqs_iqsi​ なので ci≤⌊qsi2⌋c_i\le\left\lfloor\dfrac{qs_i}{2}\right\rfloorci​≤⌊2qsi​ である。qqq は奇数なので、

C≤∑i=1k⌊qsi2⌋=∑i=1k(si⌊q2⌋+⌊si2⌋)≤g⌊q2⌋+∑i=1k(si−1)=g⌊q2⌋+g−k.\begin{align*} C &\le \sum_{i=1}^k \left\lfloor \frac{qs_i}{2}\right\rfloor \\ &= \sum_{i=1}^k \left(s_i\left\lfloor\frac q2\right\rfloor+\left\lfloor\frac{s_i}{2}\right\rfloor\right) \\ &\le g\left\lfloor\frac q2\right\rfloor+\sum_{i=1}^k(s_i-1) \\ &= g\left\lfloor\frac q2\right\rfloor+g-k. \end{align*}C​≤i=1∑k​⌊

したがって k≤g−λk\le g-\lambdak≤g−λ である。大きさ sss の連結成分を作るには少なくとも s−1s-1s−1 回の操作が必要なので、操作回数全体は少なくとも

N−k≥N−g+λN-k\ge N-g+\lambdaN−k≥N−g+λ

である。

​
⌋
2
qsi​
​
⌋
=i=1∑k​(si​⌊2q​⌋+⌊2si​​⌋)
≤g⌊2q​⌋+i=1∑k​(si​−1)
=g⌊2q​⌋+g−k.
​