0

プログラムの実行時間をできるだけ短くしたいです。

最終的なゴールは、入力Nを読み込み、評価して2つの連結リストにそれぞれ結果をストアし、その結果を順に出力することです
入力の条件は、

The first line contains the integer N. The second line contains N integers, a0,a1,...,aN−1. The integers are separated by a single space character. The third line contains N integers, b0,b1,...,bN−1. The integers are separated by a single space character.

となっています。

タイムリミットは1s,入力数は<1000000です。

現時点では、

scanf("%d", &N) //入力される要素数
for(i=0;i<N;i++)
    scanf("%d",&a[i]);
for(i=0;i<N;i++){
    scanf("%d",&b[i]); //aiの範囲を指定する数bi

for(i=0;i<N;i++){
    for(j=1;j<b[i];j++){
        if(i+j)<N){
            if(a[i+j]<a[i]){
                R[i] = (i+j) //配列に代入
            }
        }
    }
}
for(i=0;i<N;i++){
    for(j=1;j<b[i];j++){
        if((i-j)>=0){
            if((a[i-j]<a[i])){
              L[i] = (i-j) //配列に代入
            }
        }
    }
}
for(i=0;i<N;i++)
    printf("%d %d\n",L[i],R[i])//L,Rの要素をすべて出力

というようなコードを書きました。これだとTLEを返されてしまいますが、これ以外の方法が思いつかなくて詰まっている状態です。スタックを使う方法も考えてみましたが具現化できませんでした。どうかお力添えいただけると幸いです。

(今朝同じような質問をさせていただきましたが当初と質問が変わったため質問し直させていただきました。不慣れですみません。)

追記1

if(a[i+j]<a[i]){
    R[i] = (i+j) //配列に代入
}

この部分では、biの範囲中にある最も遠い(インデックスの値が大きい)ajを取得したいのでaを複数回代入することになっています

追記2
コメントで指摘いただいた点を直してみましたがやはりTLEになってしまいました…データ構造に関する問題なので上手にそれらを活用できないかな?と思っています。

5
  • 最初のダブル・ループで if((i+j)<N){...} となっている部分は else clause が無いので、for(j=1;(j<b[i])&&((i+j)<N);j++){if(a[i+j]<a[i]){...}} と書き変える事ができます。配列 b の要素の値にもよりますが、最悪でもループの実行回数は N*(N-1) になります。次に if(a[i+j]<a[i]){R[i]=(i+j)} の部分ですが、配列 a の要素の値によっては代入(R[i]=(i+j))が複数回行われる事もあり得ます。問題文の肝心の部分が記載されていないので不明なのですが、一度でも a[i+j]<a[i] が成立すれば(代入操作を行って)ループ処理を打ち切る(break loop)、という条件になっているのではないでしょうか?
    – user39889
    Commented 2020年3月29日 13:21
  • 「biの範囲中にある最も遠い(インデックスの値が大きい)ajを取得したい」とのことでしたら、for loop を decrement version にすればよろしいかと思います(配列の末尾から走査)。for(j=initial_value;end_condition;j--){...}
    – user39889
    Commented 2020年3月29日 13:47
  • 1
    ミクロな最適化を重ねても、このような課題で時間制限を満たせるようになることは滅多にありません。例えば、何らかの前処理を行っておくと、二重ループになっている処理が一重のループに書き換えられる、なんて性質が見つかるようになっているかもしれません。出来上がったコードだけ見ていてもわかりにくいので、課題の全ての設定・出題・条件等を書いていただいた方が良いように思います。
    – OOPer
    Commented 2020年3月29日 22:58
  • 1
    とりあえず提示コードは C ソースとしては不適合です(コンパイルできるはずがない)正確なコードを提示しないと、得られるはずのものも得られないですよ。
    – 774RR
    Commented 2020年3月30日 0:33
  • 1
    各変数がどのように宣言されているかはとても重要な情報です。宣言のしかたによって、Nが巨大だと正常に動かなくなったりします。
    – int32_t
    Commented 2020年3月30日 3:09

1 件の回答 1

1

現在のコードが正しいという前提では、インデックスをaの値でソートしてフェニック木(Binary Indexed Tree)の最大値、最小値版を使うのがシンプルじゃないかと思います。

フェニック木は、あるインデックスの値を変更したり(最大値版なら増やす、最小値版なら減らすのみ)、[0..i]の範囲の最大値・最小値を求めるような計算が高速に行えるデータ構造です。
(詳しくはググってください。ただしネット上の実装だとインデックスを1から始めるものとして書かれてることが多いので注意してください。下のコードは0から始まるインデックスです。)

フェニック木でa[i]未満の値のインデックスがiの位置にある状態にすると、今のコードで2重ループの内側のループになってる部分を範囲内のインデックスの最大値・最小値を求める計算に置き換えることができます。

aiをaの値で昇順にソートしたインデックスの配列(ソートにはクイックソートなど高速なソートを使ってください)、fenwick_maxを長さ N 初期値 -1 の配列、fenwick_minを長さ N 初期値 N の配列とすると、下のようなコードになります。(普段C++しか使わないのでCのコードとしては間違ってるかもしれません)

for (int i = 0; i < N; ) {
    //L, Rのセット
    //このループ内ではfenwick木にはa[ai[i]]未満の要素のインデックスしか存在しない
    for (int j = i; j < N && a[ai[i]] == a[ai[j]]; ++j) {

        //Rのセット
        //[0 .. ai[j] + b[j] - 1]の範囲の最大値を求める
        int pos = min(N - 1, ai[j] + b[ai[j]] - 1);
        int p = -1;//番兵
        //このループは最悪でもlog2(N)回程度しか繰り返さない
        while (pos >= 0) {
            p = max(p, fenwick_max[pos]);
            pos -= ~pos & (pos + 1);//pos の2進数表記で0になるビットの最も右にあるものを引く。pos == 0b01010111 なら ~pos & (pos + 1) == 0b00001000
        }
        if (ai[j] < p) {//最大値が[ai[j] + 1 .. ai[j] + b[j] - 1]の範囲にあるなら解にセット
            R[ai[j]] = ai[j] + p;
        }

        //Lのセット
        //[ai[j] - b[ai[j]] + 1 .. N - 1] の範囲の範囲の最小値を求めたいが、0からの範囲の最小値しか求められないのでインデックスを反転させ、[0, N - 1 - (ai[j] - b[ai[j]] + 1)]の範囲の最小値を求める。
        pos = min(N - 1, N - 1 - (ai[j] - b[ai[j]] + 1));
        p = N;//番兵
        while (pos >= 0) {
            p = min(p, fenwick_min[pos]);
            pos -= ~pos & (pos + 1);
        }
        if (p < ai[j]) {//最小値が範囲にあるならセット
            L[ai[j]] = ai[j] - p;
        }

    }
    //fenwick木の更新。同じ値になるインデックスを全て追加。
    for (int value = a[ai[i]]; i < N && value == a[ai[i]]; ++i) {
        int pos = ai[i];
        while (pos < N) {
            fenwick_max[pos] = max(fenwick_max[pos], ai[i]);
            pos += ~pos & (pos + 1);
        }
        pos = N - 1 - ai[i];//こちらもインデックスを反転
        while (pos < N) {
            fenwick_min[pos] = min(fenwick_min[pos], ai[i]);
            pos += ~pos & (pos + 1);
        }
    }
}

フェニック木のほかに区間木や二分木といった別のデータ構造を使う方法もありますが、ライブラリでもないと実装が大変でしょう。

あとコメントにもあるように問題に関する情報は、特に理由がなければもっとしっかり書いてほしいです。条件次第で効率のいい方法が変わったり、そもそも求めてるものと違うアルゴリズムになる可能性もあります。
特に今回時間制限超過ということですが、時間制限を超過した場合には正誤判定を行わないジャッジシステムだと、そもそも正しい結果が出るコードなのかも怪しいままです。

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

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