Codeforces Round #679 (Div. 2)

codeforces.com

A. Finding Sasuke

2個ずつのペアを0にしていけばいい
提出コード

void solve(){
    int n;
    cin >> n;
    vector<int> a(n);
    REP(i,n) cin >> a[i];
    vector<int> b(n);
    for(int i=0;i<n;i+=2){
        if(a[i] * a[i+1] < 0){
            b[i] = abs(a[i+1]);
            b[i+1] = abs(a[i]);
        }
        else{
            b[i] = -a[i+1];
            b[i+1] = a[i];
        }
    }
    REP(i,n) cout << b[i] << " ";
    cout << endl;
}

B. A New Technique

n行m列の行列からは各数字がどの列に属するか、m行n列の行列からは各数字がどの列に属するかがわかる
そのため、各数字ごとに行と列が決まるのでそれを出力すればいい
提出コード

void solve(){
    int n, m;
    cin >> n >> m;
    vector<vector<int>> a(n, vector<int>(m));
    vector<vector<int>> b(m, vector<int>(n));
    vector<int> row(n*m), colmun(n*m);
    REP(i,n) REP(j,m) cin >> a[i][j];
    REP(i,m) REP(j,n) cin >> b[i][j];
    REP(i,n){
        REP(j,m){
            row[b[j][i]-1] = i;
        }
    }
    REP(i,n){
        REP(j,m){
            colmun[a[i][j]-1] = j;
        }
    }
    vector<vector<int>> ans(n, vector<int>(m));
    REP(i,n*m){
        ans[row[i]][colmun[i]] = i+1;
    }
    REP(i,n){
        REP(j,m) cout << ans[i][j] << " ";
        cout << endl;
    }
}

C. Perform Easily

n個のノーツを引くのにどの弦とフレットを使うかは通りある
問題文の条件を満たすにはあるフレットの区間[l:r]にn個のノーツが含まれていればいい
よって、各ノーツとフレットのペア通りをフレットの昇順にソートをし、しゃくとり法でその最小区間を求めればいい
提出コード

void solve(){
    vector<int> a(6);
    REP(i,6) cin >> a[i];
    int n;
    cin >> n;
    vector<int> b(n);
    REP(i,n) cin >> b[i];
    vector<pair<int, int>> vp;
    REP(i,6) REP(j,n) vp.emplace_back(b[j] - a[i], j);
    vector<int> cnt(n);
    sort(vp.begin(), vp.end());
    int r = 0;
    int ans = INF;
    int sum = 0;
    REP(l,6*n){
        while(r < 6*n and sum < n){
            if(cnt[vp[r].second]++ == 0) sum++;
            r++;
        }
        if(sum == n) chmin(ans, vp[r-1].first - vp[l].first);
        if(--cnt[vp[l].second] == 0){
            sum--;
        }
        if(l == r) ++r;
    }
    cout << ans << endl;
}

D. Shurikens

ある一連の操作を行った後、それが条件を満たすかどうかの判定は後ろからシミュレートすると楽なことが多い気がする
この問題でも後ろからシミュレートすることを考える
まず、-の操作を考える
後ろからシミュレートする時、逆の操作になるのでxを追加する操作となる
この時、xよりも小さい値がすでにあると条件を満たさないのでNOになる
次に+の時は、今あるものから値を消す操作になる
この時、今あるものが空の場合NOとなり、そうでない場合は今持っているものの中で最小のものを消せばいい
これはsetなどを使えば値を管理できる
提出コード

void solve(){
    int n;
    cin >> n;
    vector<pair<char, int>> q;
    REP(i,2*n){
        char c;
        cin >> c;
        int p = 0;
        if(c == '-') cin >> p;
        q.emplace_back(c, p);
    }
    set<int> st;
    vector<int> ans;
    for(int i=2*n-1;i>=0;i--){
        auto [c, p] = q[i];
        if(c == '+'){
            if(st.empty()){
                cout << "NO" << endl;
                return;
            }
            ans.emplace_back(*st.begin());
            st.erase(st.begin());
        }
        else{
            if(st.lower_bound(p) != st.begin()){
                cout << "NO" << endl;
                return;
            }
            st.insert(p);
        }
    }
    cout << "YES" << endl;
    reverse(ans.begin(), ans.end());
    REP(i,n) cout << ans[i] << " ";
    cout << endl;
}