回答日:2021-11-01

質問する

質問リンク:https://www.acmicpc.net/problem/13414

アクセスと解析

最初は入力値をベクトルに入れ、find関数を使用してベクトルに存在する値をベクトルに入力し、既存の値を消去することで実現します.しかし、タイムアウトが発生した.(一般的にはfindは使えません…)
すべての入力値をvectorに挿入し、vectorの最後の値から参照し、setを使用して挿入した値をチェックします.

コード(タイムアウト)

#include <bits/stdc++.h>

using namespace std;

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    
    int K, L;
    cin >> K >> L;
    
    vector<string> v;
    
    for (int i = 0; i < L; i++) {
        string str;
        cin >> str;
        
        auto it = find(v.begin(), v.end(), str);
        if (it != v.end()) {
            v.erase(it);
        }
        v.push_back(str);
    }
    for (int i = 0; i < K; i++) {
        cout << v[i] << '\n';
    }
    return 0;
}

コード(通過)

#include <bits/stdc++.h>

using namespace std;

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    
    int K, L;
    cin >> K >> L;
    
    vector<string> v, ret;
    set<string> st;
    
    for (int i = 0; i < L; i++) {
        string str;
        cin >> str;
        v.push_back(str);
    }
    for (int i = v.size() - 1; i >= 0; i--) {
        if (st.find(v[i]) == st.end()) {
            st.insert(v[i]);
            ret.push_back(v[i]);
        }
    }
    for (int i = ret.size() - 1; i >= 0 && K > 0; i--, K--) {
        cout << ret[i] << '\n';
    }
    return 0;
}

結果

フィードバック

問題を解くとき、いろいろなSTLを使う練習をします.