解説
回のワープは、回以上の同じ頂点集合のループで構成されています。これは、開始地点と終了地点が同じであることから導かれます。
ワープ回数 と 総電力消費量 は、ループ回数を項として共有しています。
よって、はの約数であることがわかります。
ループに含まれる頂点集合の大きさを, 電力消費量の総和をとします。またの範囲に含まれる整数の総和をとします。
開始地点の条件から、ループの頂点集合には必ず含まれないといけません。であり、 を満たすような であれば、とを満たす順列を構成することができます。
まず、整数の配列が与えられたときに
を満たす順列を構築する方法を考えます。
これは、配列を環にして、頂点をを満たす最小のの頂点に向かせることで、実現できます。
次に
を満たす長さの配列を構築する方法を考えます。
これは、以下の手順により、貪欲に作ることができます。
- 先頭個の要素のみであり、他はであると配列を初期化します。この時点で、は下限です。
- まだ触れていない後ろの桁から、必要な分だけ後ろの桁に降ろすことを続けます。
よって、この問題はで解くことができます。
ユーザー解説
ユーザー解説を書くユーザー解説はまだありません。