競プロ日記#25/03/31

アルゴ式-タイルの敷き詰め

• この問題も結局は最後の状態から追っていく
• i-1,i-2,i-3がそれぞれ0以上かどうかで場合分け
• 解説にもあるがdp変数をN+1（0~Nまで）で作って便宜的にdp[0]を1としないといけなさそう。なんとかdp[1] = 1からやる方法を少しだけ考えたがどうにも手詰まりっぽい

 vector<int> dp(N + 1, 0);
dp[0] = 1;
for (int i = 1; i <= N; ++i) {
    if (i-1 >= 0) dp[i] += dp[i-1];
    if (i-2 >= 0) dp[i] += dp[i-2];
    if (i-3 >= 0) dp[i] += dp[i-3];
}
cout << dp[N] << endl;

アルゴ式-よい数列にせよ

• 正直問題の時点でなかなか難しそうで面食らってしまった。
• 全削除する場合と一部削除するのが混ざってるのがしんどい気がした
• 確認問題で解説もないので仕方なくGPT先生に聞いた。以下がGPT先生が生成したコードの一部

int minDeletionsToSatisfyCondition(const vector<int>& A) {
    unordered_map<int, int> count;  // 整数の出現回数を保持するマップ
    int deletions = 0;

    // 数列 A の各整数の出現回数をカウント
    for (int num : A) {
        count[num]++;
    }

    // 出現回数ごとに削除する必要がある回数を計算
    for (const auto& entry : count) {
        int value = entry.first;
        int cnt = entry.second;

        // value より少ない回数しかない場合、その数はすべて削除
        if (cnt < value) {
            deletions += cnt;  // 全部削除
        } else {
            // value より多く出現している場合、value 回に調整するための削除
            deletions += cnt - value;
        }
    }

    return deletions;
}

• mapで管理してkeyを整数値、valueをその出現回数として管理してfor文で
• というか

// 数列 A の各整数の出現回数をカウント
for (int num : A) {
    count[num]++;
}

• vector→mapへのカウントの置き換えをこれで済ませてるのが地味だけど感嘆した。
• わざわざこのロジックのために別関数まで定義する必要もなくもっと別の解法もあったかもしれないがとりあえずは考え方というか道筋が知りたかったのでこれで