競プロ日記#25/04/08

アルゴ式-部分列チェッカー

• 部分文字列とは違うということとあくまでも部分列なので順番は順守しなければならない部分がポイント

// Sの中でTを順番に探す
while (i < N && j < M) {
    if (S[i] == T[j]) {
        j++;  // Tの次の文字を探す
    }
    i++;  // Sの次の文字を調べる
}

// jがTの長さに達していれば、TはSの部分列
    return j == M;

• 二つの文字列についてi,jの2つのカウンターで並行的に走査していくのがポイント
• これに近い実装はできたがイマイチ答えが合わなかった。GPT先生に聞いた。

アルゴ式-メモ化のメリット (1)

• さほど難しくないのだが各整数が呼ばれた回数を記録するカウンターの管理が適切ではなかった。
• 私は以下の様にmain関数内で定義したカウンタを参照渡しで渡す形にしてしまった。

int rec(int n, vector<int>& vec){
    
    vec[n - 1]++;
    if (n == 1 or n == 2){
        return 1;
    }else{
        return rec(n - 2,vec) + rec(n - 1,vec);
    }
}

• 解説ではグローバルで定義した配列をそのまま操作していた。

vector<int> counter(X+1);

int rec(int n) {
    counter[n]++;
    if (n==1 || n==2) {
        return 1;
    }
    else {
        return rec(n-2) + rec(n-1);
    }
}