質問: プログラムの実行時間をできるだけ短くしたいです。 最終的なゴールは、入力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=0){ if((a[i-j]
回答: 現在のコードが正しいという前提では、インデックスを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); } } } ``` フェニック木のほかに区間木や二分木といった別のデータ構造を使う方法もありますが、ライブラリでもないと実装が大変でしょう。 あとコメントにもあるように問題に関する情報は、特に理由がなければもっとしっかり書いてほしいです。条件次第で効率のいい方法が変わったり、そもそも求めてるものと違うアルゴリズムになる可能性もあります。 特に今回時間制限超過ということですが、時間制限を超過した場合には正誤判定を行わないジャッジシステムだと、そもそも正しい結果が出るコードなのかも怪しいままです。