実行時間を要する場所がわからない

Question

AtCoderのC-Choose Elementsで一部TLEになってしまいます。どの部分が時間を要しているのか、どのように改善すれば良いのかご教授いただきたいです。よろしくお願いします。

問題：https://atcoder.jp/contests/abc245/tasks/abc245_c

【プログラムの説明】
入力の読み込みを行う。
スタックを用いる。
二つの配列tmp2,3の初めの要素二つをスタックに入れる。
スタックの上の要素を見て、絶対値差が条件に合っているものを順次入れていく。
（countはスタック中の要素がtmp2,3で何番目に値するのかを記憶しておくもの）
（pointは行き止まりにあたった時にすぐに分岐に戻れるように分岐点の添え字を記憶しておくもの）
行き止まりにあたると、記憶して置いた分岐点まで戻り、間違いの道をNaNとして選べないようにしてから再度同じ操作を行う。

const fs= require('fs');

function Main(input){
    input=input.split("\n");
    var tmp1=input[0].split(" ");
    var tmp2 = input[1].split(" ");
    var tmp3=input[2].split(" ");
    for(var i=0;i<tmp1.length;i++){
        tmp1[i]=parseInt(tmp1[i]);
    }
    for(var i=0;i<tmp2.length;i++){
        tmp2[i]=parseInt(tmp2[i]);
    }
    for(var i=0;i<tmp3.length;i++){
        tmp3[i]=parseInt(tmp3[i]);
    }

    var a=new Array(tmp1[1]);
    var count=new Array();
    var t=0, s=0;
　 var point=new Array();
    var k=0, num=0;

    a[t]=tmp2[s];
    count[t]=s;
    a[++t]=tmp3[s];
    count[t]=s;

    point[k]=s;
    while(1){
        if(num===0){
            if(Math.abs(tmp2[s+1]-a[t])<=tmp1[1] && Math.abs(tmp3[s+1]-a[t])<=tmp1[1]){
                a[++t]=tmp2[++s];
                point[++k]=t;
                count[t]=s;
                a[++t]=tmp3[s];
                count[t]=s;
            }else if(Math.abs(tmp2[s+1]-a[t])<=tmp1[1]){
                a[++t]=tmp2[++s];
                count[t]=s;
            }else if(Math.abs(tmp3[s+1]-a[t])<=tmp1[1]){
                a[++t]=tmp3[++s];
                count[t]=s;
            }else{
               t=point[k--];
               num++;
            }
            if(s===tmp1[0]-1){
                console.log('Yes');
                return;
            }
        }else{
            if(k<-1){
                console.log('No');
                return;
            }
            if(a[t+1]===a[t]){
                t=point[k--];
            }else{
                s=count[t];
                if(tmp2[s+1]===a[t+2]){
                    tmp2[s+1]=NaN;
                }else if(tmp3[s+1]===a[t+2]){
                    tmp3[s+1]=NaN;
                }
                num=0;
            }
        }
    }
}

Main(fs.readFileSync("/dev/stdin", "utf-8"));

Comments

[退会済みユーザー]

タグの C#, C++ は関係ないのでは？ 関係なければ外してください。タグで見ている人の迷惑になりますので。関係あるならどのように関係するのか書いてください。

[TKG000]

すみません。修正致しました。

[1T2R3M4]

プロファイリングでもしてみては。、

[TKG000]

ありがとうございます。
ループごとに時間を計測してみます。

Answer 1

分岐している個所だけにNaNを入れるのではなく、分岐している箇所に至るすべての箇所にNaNを入れるようにすれば、今のコードでもそれなりに速くなります。(メモ化と同様の効果が見込めるため)

現状、分岐している箇所にしかNaNを入れていないため、常に一方の選択肢は残り続けることになります。例えば、以下のような入力の場合に、1しかNaNに書き換えられません。そうなると、別のルートを試す際に毎回2を末尾までたどらなければならず、O(N^2)の時間がかかってしまいます。(入力例は長くなりすぎるので省略しています)

200000 1
2 2 ... 2 4
1 1 ... 1 4

Comments

[TKG000]

一度たどった道をつぶしておくという方法は時間の短縮になりますね。一度試してみます。
回答ありがとうございます。

Answer 2

「戻る」発想が間違いです。「戻る」ことで不必要な計算をして、処理時間を超過しています。
戻らない処理を考えてみてください。

Comments

[TKG000]

ありがとうございます。

[k08045kk]

説明が悪かったかもしれない。
「不必要な計算」は「同じ計算の繰り返し」の意味であって、「巻き戻し等の補足的な計算」のことを指しているわけではないのであしからず。
（「再帰」処理は、関数呼び出しのオーバーヘッドとかでもっと悪い状態になるのでは？）

[TKG000]

試したところそうでした...
やはり自分の考えを改良するだけでは解決できないのではと思いほかの解答を参考にすることにしました。
ありがとうございます。