競プロ日記#25/04/28

アルゴ式-部分和問題

• 誘導があるのでそのまま実装するのはそこまで難しくないがそもそも概念がなかなか理解できていない。
• 解説を読んでGPTに入れてみてやっと理解できた。
• がしかし多分ものにはできていない。何度も復習しないと自分で応用はできない

アルゴ式-部分和問題のメモ化

• むずすぎる。ティルトしてるからなのか難しいからなのかわからないが解説読んでやっと理解できる。

アルゴ式-荷物と箱

• 久々に解説見ないでちゃんと実装できた気がする
• とはいえイテレータの理解はもう少し深めたい
• そもそもこの実装は大きいものから順に入れていったが本来は小さいものから入れていかないと事故る可能性がある気がする

int main() {
    int N, M;
    cin >> N >> M;
    vector<int> A(N), B(M);
    for (int i = 0; i < N; i++) cin >> A[i];
    for (int i = 0; i < M; i++) cin >> B[i];
    sort (A.rbegin(), A.rend());
    int ans = 0;
    for (int i = 0; i < N; i++) {
        auto it = lower_bound(B.begin(), B.end(), A[i]);
        if (it != B.end()) {
            ans++;
            B.erase(it);
        }
    
    }
    cout << ans << endl;
}

アルゴ式-区間スケジューリング問題

• 貪欲法の考え方が詰まった問題らしい。
• 終了時刻が早い予定を優先的に選んでいくのが良いらしい