2

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

自分で書いたコード

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

}

サンプル

#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;
    }
}
2
  • 1)メモリ時間とは実行時間のことでしょうか。2)どのデータで実行したかわかりますか。 ※私の環境で、リンクされたページの入力例で計測したところ、差異がみられませんでした。mainを修正して10000回ループで実行してみました。 Commented 2019年9月10日 11:49
  • testcase #3です。メモリ時間とは実行時間のことです。恐らく下記の回答をしてくれた方々の言う通りにtestcase の Nが大きくなるとiteratorのループ数が大きくなるようなので、大きいtestcaseでないと、差異が分からないと思います(小さいテストケースでは自分で書いたコードのほうが効率が良いこともあるようですEx, sample case)。
    – Ranger
    Commented 2019年9月10日 14:38

3 件の回答 3

1

ぱっと見て感じですが…

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

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

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

1

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

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

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

#! /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を使っています
1

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

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

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

一方「サンプル」の場合、Mのループ内でliteratorは前の位置から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と思います。

1
  • つまり、私のコードの実行時間は最悪の場合,(log N)*Mで他方サンプルの実行時間はM*maximum_a_i (0<=maximum_a_i<=100)ということでしょうか?
    – Ranger
    Commented 2019年9月11日 7:57

この質問に回答するには、ログインする必要があります。

求めていた回答ではありませんか? のタグが付いた他の質問を参照する。