Hackerrankのチャレンジのタイムアウト

Question

ちょっとハッカーの問題を解決しようとしていますが、いくつかのテストケースではコードのタイムアウトと私はなぜわかりません。 This is the challenge。

そして、ここに私のコードです：

#include <math.h> 
#include <stdio.h> 
#include <string.h> 
#include <stdlib.h> 
#include <assert.h> 
#include <limits.h> 
#include <stdbool.h> 

int main(){ 
    int n, k, q; 
    scanf("%d %d %d",&n,&k,&q); 
    int qs[q]; 
    int a[n]; 

    for(int i = 0; i < n; i++){ 
     scanf("%d", &a[i]); 
    } 


    for(int i = 0; i < q; i++){ 
     scanf("%d",&qs[i]); 
    } 

    int lastNbr = a[n-1]; 
    for(int i = 0; i < k; i++){ 
     lastNbr = a[n-1]; 
     for(int j = n - 1; j > -1; j--){ 
      a[j] = (j-1 >= 0) ? a[j-1] : lastNbr; 
     } 
    } 

    for(int i = 0; i < q; i++){ 
     printf("%d\n", a[qs[i]]); 
    } 

    return 0; 
} 

Answer 1

すべての権利は、あなたのアルゴリズムの時間計算量を分析することで起動できます：

あなたが回転する2は、常にn * k操作のために行くループの入れ子になっていあなたの配列k回と回転を行うためにn操作が必要です。

これはO(n * k)となるので、最悪の場合の入力では約10^10であり、これは非常に多くの操作です。

アルゴリズムの複雑さを計算する方法については、最初にthis記事をお読みください。非常に有用な情報が提供されており、実際の例で説明しています。

ここで、アルゴリズムを再考し、時間の複雑さを改善する必要があります。私はあなたに解決策を躊躇させませんが、私はあなたにヒントを与えることができます：k単位を1単位で回転させる必要はないと思ってください。代わりにk単位で1回だけ行うことができます。

願わくばこれは、チャレンジの解決に役立ちます。 :)

Answer 2

あなたのコードを見れば、それはo（n * k）の解です。あなたはそれをo（n）時間で解決することができます。そして、入力サイズは10パワ5です。そのため、タイムアウトエラーが発生しています。 ％があなたを助けます。