65231


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

最終的なゴールは、入力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です。

現時点では、

[code]

    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の要素をすべて出力
    
[/code]

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

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

追記1

[code]

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

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

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


CC BY-SA 4.0
2020-03-29T12:18:29.087
65203
2020-03-30T07:07:50.173
2020-03-29T18:50:00.380
38330
38330
question
c アルゴリズム スタック
プログラムの実行時間をできるだけ短くしたい


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

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

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

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

[code]

    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);
            }
        }
    }
    
[/code]

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

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


CC BY-SA 4.0
2020-03-30T07:07:50.173
65231
2020-03-30T07:07:50.173
33033
65203
answer