

下のコードは、競技プログラミングの問題
[バトンリレーゲーム](https://onlinejudge.u-aizu.ac.jp/challenges/sources/PCK/Prelim/0301?year=2014)
に対する回答です。サンプルはリストを使用したものを載せました。  
同じテストケースでサンプルコードはメモリ時間0.03sだったのに対し自分のコードは1.99sを超えTLE (Time Limit Exceeded)
となりました。  
しかし、この二つのコードの根本的違いが判りません。どなたかご教授願えないでしょうか？

自分で書いたコード

[code]

    #define _USE_MATH_DEFINES
    #include<math.h>
    #include<deque>
    #include<queue>
    #include<vector>
    #include<algorithm>
    #include<iostream>
    #include<set>
    #include<cmath>
    #include<tuple>
    #include<string>
    #include<chrono>
    #include<functional>
    #include<iterator>
    #include<random>
    #include<unordered_set>
    #include<array>
    #include<map>
    #include<iomanip>
    #include<assert.h>
    #include<bitset>
    #include<stack>
    #include<memory>
    #include<list>
    
    #define INF (1e9)
    #define rep(i,n) for(int i=0;i<n;i++)
    
    using namespace std;
    typedef long long ll;
    typedef pair<double long, ll>P;
    
    int N, M, Q, a[200000], q[100000]; list<int> stu;
    int V[2000000];
    int main() {
    
        cin >> N >> M >> Q;
        rep(i, M) {
            cin >> a[i];
    
        }
    
        rep(i, N) {
    
            stu.push_back(i);
        }
        int st = 0;
        rep(i, M) {
    
            if (a[i] % 2) {
                int x = st - a[i];
                //cout << x << "sub" << endl;
                x %= (N - i);
                x += N - i;
                x %= (N - i);
    
                list<int>::iterator itr = stu.begin();
                rep(i, x) {
                    itr++;
                }
                int y = *itr;
                stu.erase(itr);
                //cout << x <<" ee"<< endl;
    
                V[y] = 1;
                st = x;
            }
            else {
                int x = st + a[i];
                x %= (N - i);
                //cout << x << endl;
                auto itr = stu.begin();
                rep(i, x) {
                    itr++;
                }
                int y = *itr;
                V[y] = 1;
                stu.erase(itr);
                st = x;
            }
        }
    
    
    
        rep(i, Q) {
                cin >> q[i];
    
            if (!V[q[i]]) {
                cout << 1 << endl;
            }
            else {
                cout << 0 << endl;
            }
        }
    
    }
    
[/code]

サンプル

[code]

    #define _USE_MATH_DEFINES
    #include<math.h>
    #include<deque>
    #include<queue>
    #include<vector>
    #include<algorithm>
    #include<iostream>
    #include<set>
    #include<cmath>
    #include<tuple>
    #include<string>
    #include<chrono>
    #include<functional>
    #include<iterator>
    #include<random>
    #include<unordered_set>
    #include<array>
    #include<map>
    #include<iomanip>
    #include<assert.h>
    #include<bitset>
    #include<stack>
    #include<memory>
    #include<list>
    
    #define INF (1e9)
    #define rep(i,n) for(int i=0;i<n;i++)
    
    
    using namespace std;
    typedef long long ll;
    typedef pair<double long, ll>P;
    
    
    #define MAX 1000000
    int N, M, Q;
    int A[MAX];
    int V[MAX];
    
    int main() {
        cin >> N >> M >> Q;
        for (int i = 0; i < M; i++) cin >> A[i];
        for (int i = 0; i < N; i++) V[i] = 1;
        list<int> l;
        for (int i = 0; i < N; i++) l.push_back(i);
        list<int>::iterator it = l.begin();
        for (int i = 0; i < M; i++) {
            int a = A[i];
            if (a % 2 == 0) {
                for (int c = 0; c < a; c++) {
                    it++;
                    if (it == l.end()) it = l.begin();
                }
            }
            else {
                for (int c = 0; c < a; c++) {
                    if (it == l.begin()) {
                        it = l.end();
                        it--;
                    }
                    else {
                        it--;
                    }
                }
            }
            V[*it] = 0;
            it = l.erase(it);
            if (it == l.end()) it = l.begin();
        }
        for (int i = 0; i < Q; i++) {
            int q; cin >> q;
            cout << V[q] << endl;
        }
    }
    
[/code]


CC BY-SA 4.0
2019-09-10T08:26:01.707
57963
2019-09-11T08:55:44.827
2019-09-10T11:05:29.307
19110
24617
question
c++ アルゴリズム
なぜこのコードはTLEになる？


「自分で書いたコード」の変数「`stu`」と「サンプル」の変数「`l`」(どちらも`list<int>`)の現在位置の維持の仕方の効率の違いと予想します。

「自分で書いたコード」の場合、`M`のループ内で`stu`の`iterator`を常に`begin()`から該当位置に移動させようとしているため、`N`の値が大きくなればなるほど、移動させるのにかかる時間がかかると予想します。  
(つまり、絶対位置で維持しようとしている)

＃問題文で言えば、「バトンの位置を常に(便宜上の)先頭の人から最終位置まで渡す」イメージ。

一方「サンプル」の場合、`M`のループ内で`l`の`iterator`は前の位置から`A[k]`の値分しか移動させないので、移動させるのに時間がかかってないと予想します。  
(つまり、相対位置で維持しようとしている)

いかがでしょうか?

＃蛇足かも知れませんが、random iteratorが使える`vector`などでは、移動に「`itr +=
x`」と書いて定数時間で位置を移動できるので、「自分で書いたコード」が高速になるかも知れません。ただし、`erase()`のコストが上がるので、本当に高速になるかは試してみないとわからないです。

# コメントに対する追記

> 私のコードの実行時間は最悪の場合,`(log N)*M`で他方サンプルの実行時間は`M*maximum_a_i`
> `(0<=maximum_a_i<=100)`ということでしょうか？

「私のコード」の場合、もっと悪くなると思います。

具体的には、「私のコード」の場合、`M`のループ内の処理ごとに、最悪`N`回iteratorを移動させる可能性があるので、計算量としては「`N *
M`」と考えたほうがよいと思います。(実装では、`itr++`を繰り返しているので、末尾まで移動するコストは`log(N)`ではなく`N`と思います)

＃`M`回の試行で、全員が「1」を宣言するのが最悪ケースと思います。  
＃厳密には、「`N * (N - 1) * (N - 2) * ... * (N - M)`」ですが、大まかに言っています。

「サンプル」の場合、コメント通り`M * maximum_a_i`と思います。


CC BY-SA 4.0
2019-09-10T10:16:59.010
57966
2019-09-11T08:55:44.827
2019-09-11T08:55:44.827
20098
20098
57963
answer


ぱっと見て感じですが…

次のバトンが渡される人を見つけるとき、

質問者のコード: 毎回始めの`stu.begin()`から辿っている。  
サンプルのコード: 抜けた人の次の人から辿っている。

という違いがあります。問題の注目すべき点は各生徒が宣言する数はたかだが100以下(`N`の最大値に比べて極めて小さい)であるということです。質問者のコードではイテレーターのインクリメントする回数がぐるっと回って`N`に近い値になる可能性がありますが、サンプルコードは常に100以下になります。ここら辺の違いが大きいと思われます。


CC BY-SA 4.0
2019-09-10T10:19:27.093
57967
2019-09-10T10:19:27.093
7347
57963
answer


質問者さんのコードで`N-i`で割った余りを取っているのは、時計回りでの移動距離を算出するという意図があると推察します。この余りは最大で`N-i-1`なので、イテレータの加算回数も、各ループごとにO(N)=200000回ぐらい必要になってしまいます。例えば(余りを取る前の)`x`が小さな負の値になるようにすればこのような状況を作れてしまいます。

本来は、ループごとに時計回り・反時計回りに高々100だけ移動すればよいです。（多分サンプルコードもそうなっていると思います。）

次のようなPythonコードで生成した入力を与えてみると実行時間の違いを実感できます。  
(余りを取ったあとの`x`がどのような値になるかも観察してみてください。)

[code]

    #! /usr/bin/python3
    import random
    
    n = 200000
    m = n-1
    q = 1
    print(n,m,q)
    for _ in range(m):
        print(5,end=" ")
    print()
    print(0)
    # 次のような出力を意図
    # 200000 199999 1
    # (199999個の5)
    # 0
    # 
    # st - a[i]を負にするつもりで奇数5を使っています
    
[/code]


CC BY-SA 4.0
2019-09-10T10:48:46.657
57968
2019-09-10T11:17:35.220
2019-09-10T11:17:35.220
13199
13199
57963
answer