外部サイトへ移動します

リンク先の URL を確認してから開いてください。

別タブで開く

解説

S - Power PAKUPAKU Warp Device

作成者 nekooooooo、siooisi、jammy、trueryob

テスター siooisi、tau0529、trueryob

配点 525 点

実行時間制限
2.2 秒
メモリ制限
222 MiB

解説

MM回のワープは、11回以上の同じ頂点集合のループで構成されています。これは、開始地点と終了地点が同じであることから導かれます。

ワープ回数 MM と 総電力消費量 WW は、ループ回数CCを項として共有しています。

よって、CCはgcd⁡(M,W)\gcd(M, W)の約数であることがわかります。

ループに含まれる頂点集合の大きさをZZ, 電力消費量の総和をSSとします。また[l,r][l, r]の範囲に含まれる整数の総和をf(l,r)f(l, r)とします。

開始地点の条件から、ループの頂点集合に11は必ず含まれないといけません。1≤Z≤N1 \leq Z \leq Nであり、f(1,Z)≤S≤1+f(N−Z+2,N)f(1, Z) \leq S \leq 1 + f(N-Z+2, N) を満たすような CC であれば、MMとWWを満たす順列を構成することができます。

まず、整数の配列AAが与えられたときに

Ai=Aj  ⟺  Pにてiとjが同じ連結成分に含まれるA_i = A_j \iff P \text{にて} i\text{と}j\text{が同じ連結成分に含まれる}

を満たす順列PPを構築する方法を考えます。

これは、配列AAを環にして、頂点iiをAi=Aj,i≤jA_i = A_j, i \leq jを満たす最小のjjの頂点に向かせることで、実現できます。

次に

Bi∈{0,1}B_i \in \{0, 1\}

∑i×Bi=S\sum i \times B_i = S

∑Bi=Z\sum B_i = Z

を満たす長さNNの配列BBを構築する方法を考えます。

これは、以下の手順により、貪欲に作ることができます。

  1. 先頭ZZ個の要素のみ11であり、他は00であると配列を初期化します。この時点で、∑i×Bi\sum i \times B_iは下限です。
  2. まだ触れていない後ろの桁から、必要な分だけ後ろの桁に降ろすことを続けます。

よって、この問題はO(N+M)O(N + \sqrt{M})で解くことができます。

ユーザー解説

ユーザー解説を書く

ユーザー解説はまだありません。