構造体Loop
初めに
独自で実装している構造体Loopについて書いておきます(C++です)。
AtCoderでこの構造体を使用して解ける問題が何度か出題されています。
一応、いくつかの問題でACは取れていますが、素人の実装なので、誤りがある場合があります。ご了承ください。
概要
個の元を持つ集合とその写像が以下の条件を満たすとします。
である初期値が与えられ、ここから写像を求めることを繰り返すような処理についての以下のクエリを、の前処理をしておくことで、それぞれで答えられます。
基本的にはを想定しています。
集合は構造体内では定義されていません。写像を構造体内に記述し、写像を求める中で得られた値のみを配列V
に記録していきます。
コンストラクタ
Loop<T, mapping> lp
- 写像
mapping
を定義する必要があります。
T mapping(T x) { /* xが与えられた時のf(x)の内容を書く */ }
制約
型
T
は、unordered_map
で同一かどうかの判定ができればよい集合のサイズは以下くらい(そうでないと、多くの問題で
TLE
になる可能性が高い)
build
void lp.build(T t)
クエリに答えるための前計算です。
後述するget
やcount
の呼び出し前に実行する必要があります。
初期値t
から写像を求めることを繰り返し、写像として得られた値が順番に配列V
に記録されます。同じ値に2回なった時点で処理が終了します。
計算量
get
T lp.get(long long k)
初期値t
からk
回写像を求めた後の値を返します。
計算量
count
vector<long long> lp.count(long long k)
初期値t
からk
回写像を求める時、V
の各要素から何回写像を求めたかをカウントします。
計算量
実装
表示
template<class T, T (*mapping)(T)>
struct Loop {
long long s, // ループのスタート
e, // ループの最後+1 (初めて重複した値が出現した場所)
l; // ループの長さ
vector<T> V; //非ループ部とループ部を記録
unordered_map<T,long long> mp; //値が2回現れたかを調べる
void build(T t) {
while (1) {
if (mp.count(t)) {
s = mp[t];
e = (long long) V.size();
l = e - s;
break;
}
mp[t] = (long long) V.size();
V.emplace_back(t);
t = mapping(t);
}
}
/*
build呼び出し後に使用する
写像をk回求めた時のt'を返す
*/
T get(long long k) {
if (k < s) return V[k];
k = (k - s) % l;
return V[s + k];
}
/*
build呼び出し後に使用する
k回まで写像を求めた時に各値に何回なったかをカウントする
*/
vector<long long> count(long long k) {
int size = (int) V.size();
vector<long long> res(size, 0);
for (int i = 0; i < min(s,k); i++) res[i] = 1; //非ループ部
k -= s;
if (k <= 0) return res;
long long q = k / l, r = k % l;
for (int i = s; i < e; i++) res[i] = q;
for (int i = s; i < s + r; i++) res[i]++;
return res;
}
};
アルゴリズム
前処理について
という条件を満たす場合、写像を求めることを繰り返すと、同じ値が2回出た時点で以後ループします。
同じ値となったものをとおきます。
について、
- 1回目に出現した位置を
- 2回目に出現した位置を
- 右半開区間に含まれる元の数を
とします。
また、が2回出現する直前までに出現した値を出現順で並べたものを、
とします。
写像を求めることを繰り返しても、となるのは高々1回です。この部分を非ループ部と呼ぶことにします。
非ループ部のサイズは、です。
の部分は、この後写像を求め続けるととなるためループします。これをループ部と呼ぶことにします。
ループ部のサイズは、です。
前処理にかかる計算量ですが、鳩の巣原理から高々回写像を求めると同じ値になります。このため、です。
getについて
回写像を求めた後の値が、非ループ部かループ部によって場合分けします。
非ループの場合
が成り立つ場合、最終的に非ループ部の値となり、それはです。ループ部の場合
回移動すると、となります。残り、回の移動後にループ部のどの値になるかが分かればよいです。
これは以下の問題と同じです。
- 数列を時計回りに並べ、時計回りに1つずつ進むことを考える。から回進むとどの元に到達するか。
この問題のようにまで進むとに戻る場合、をとればどこに行くかわかります。
すると、はからのオフセットとなるので、となります。
計算量はです。
countについて
非ループ部からは、1回しか写像を求めることはありません。そのため、の場合、を満たす番目が+1ずつされます。
の場合を考えます。
非ループ部は全て1となります。
ループ部について、写像を求める残り回数は、となります。
となるを求めます。、です。
これは、ループ部を周して、残り回写像を求めることに対応します。
よって、ループ部については、全て加算され、更にを満たす番目に+1されます。
以上から、の各元について、一回の計算で何回写像が求められたかがわかるので、です。
AtCoderでの過去問でLoopを使える問題
ネタバレ注意