geam1113’s diary

主にAtcoderのコンテストの備忘録を書きます。AtCoder緑と水色を行ったり来たりしています。

構造体Loop

初めに

独自で実装している構造体Loopについて書いておきます(C++です)。
AtCoderでこの構造体を使用して解ける問題が何度か出題されています。
一応、いくつかの問題でACは取れていますが、素人の実装なので、誤りがある場合があります。ご了承ください。

概要

N個の元を持つ集合Aとその写像fが以下の条件を満たすとします。

  • f:A\longrightarrow A

t\in Aである初期値tが与えられ、ここから写像を求めることを繰り返すような処理についての以下のクエリを、O(N)の前処理をしておくことで、それぞれO(1),\ O(N)で答えられます。

  • K写像を求めた時の元x
  • K写像を求める過程でAの各元aからそれぞれ何回写像を求めたか

基本的にはf:\{0,\ 1,\ \cdots ,\ N-1\} \longrightarrow \{0,\ 1,\ \cdots ,\ N-1\}を想定しています。

集合Aは構造体内では定義されていません。写像を構造体内に記述し、写像を求める中で得られた値のみを配列Vに記録していきます。

コンストラク

Loop<T, mapping> lp

を定義する必要があります。

T mapping(T x) {
    /* xが与えられた時のf(x)の内容を書く */
}

制約

  • T は、unordered_mapで同一かどうかの判定ができればよい

  • 集合Aのサイズは10^7以下くらい(そうでないと、多くの問題でTLEになる可能性が高い)

build

void lp.build(T t)

クエリに答えるための前計算です。
後述するgetcountの呼び出し前に実行する必要があります。

初期値tから写像を求めることを繰り返し、写像として得られた値が順番に配列Vに記録されます。同じ値に2回なった時点で処理が終了します。

計算量

  • O(N)

get

T lp.get(long long k)

初期値tからk写像を求めた後の値を返します。

計算量

  • O(1)

count

vector<long long> lp.count(long long k)

初期値tからk写像を求める時、Vの各要素から何回写像を求めたかをカウントします。

計算量

  • O(N)

実装

表示

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;
    }
 
};

 

アルゴリズム

前処理について

f:A\longrightarrow Aという条件を満たす場合、写像を求めることを繰り返すと、同じ値が2回出た時点で以後ループします。
同じ値となったものをxとおきます。

xについて、

  • 1回目に出現した位置をs
  • 2回目に出現した位置をe
  • 右半開区間[s,e)に含まれる元の数をl

とします。
また、xが2回出現する直前までに出現した値を出現順で並べたものを、

V=\{V_0,\ V_1,\ \cdots ,\ V_s,\ \cdots ,\ V_{e-1}\}

とします。

写像を求めることを繰り返しても、V_0,\ V_1,\ \cdots ,\ V_{s-1}となるのは高々1回です。この部分を非ループ部と呼ぶことにします。
非ループ部のサイズは、sです。

V_s,\ V_{s+1},\ \cdots ,\ V_{e-1}の部分は、この後写像を求め続けるとV_s = V_eとなるためループします。これをループ部と呼ぶことにします。
ループ部のサイズは、lです。

前処理にかかる計算量ですが、鳩の巣原理から高々N写像を求めると同じ値になります。このため、O(N)です。

getについて

K写像を求めた後の値が、非ループ部かループ部によって場合分けします。

  • 非ループの場合
    K\lt sが成り立つ場合、最終的に非ループ部の値となり、それはV_Kです。

  • ループ部の場合
    s回移動すると、V_sとなります。残り、K-s回の移動後にループ部のどの値になるかが分かればよいです。

これは以下の問題と同じです。

  • 数列V'=\{V'_0,\ V'_1,\ \cdots ,\ V'_{l-1}\}を時計回りに並べ、時計回りに1つずつ進むことを考える。V'_0からK'回進むとどの元に到達するか。

この問題のようにl-1まで進むと0に戻る場合、K'\ mod\ lをとればどこに行くかわかります。

p = (K-s)\ mod\ lすると、pV_sからのオフセットとなるので、V_{s+p}となります。

計算量はO(1)です。

countについて

非ループ部からは、1回しか写像を求めることはありません。そのため、K\leq sの場合、i\lt Kを満たすi番目が+1ずつされます。

K\gt sの場合を考えます。
非ループ部は全て1となります。

ループ部について、写像を求める残り回数K'は、K' \leftarrow K - sとなります。
K'=ql+rとなるq,rを求めます。q = \lfloor \frac{K'}{l} \rfloorr = K' \ mod\ lです。

これは、ループ部をq周して、残りr写像を求めることに対応します。

よって、ループ部については、全てq加算され、更にs\leq i \lt s+rを満たすi番目に+1されます。

以上から、Vの各元について、一回の計算で何回写像が求められたかがわかるので、O(N)です。

AtCoderでの過去問でLoopを使える問題

ネタバレ注意

表示

ABC258E Packing Potatoes 問題 実装

ABC241E Putting Candies 問題 実装

ABC167D Teleporter 問題 実装