Educational Codeforces Round 90 (Rated for Div. 2)

codeforces.com

A. Donut Shops

読解が辛い
のとき1つ目のお店のほうが小さくなる個数は存在しない
のとき2つ目のお店のほうが小さくなる個数は存在しない
それ以外の時、1つ目のお店では1個買う時必ず小さくなり、2つ目のお店ではb個買う時必ず小さくなる
提出コード

void solve(){
    ll a, b, c;
    cin >> a >> b >> c;
    if(a >= c){
        cout << -1 << " " << b << endl;
    }
    else if(a * b <= c){
        cout << 1 << " " << -1 << endl;
    }
    else{
        cout << 1 << " " << b << endl;
    }
}

B. 01 Game

操作回数は操作順によらず一定なのでその偶奇で勝敗が決まる
操作回数はstackなどでシミュレートすればいい
提出コード

void solve(){
    string s;
    cin >> s;
    vector<int> st;
    int cnt = 0;
    REP(i,s.size()){
        if(st.empty()) st.push_back(s[i]-'0');
        else{
            if(st.back() != (s[i] - '0')){
                cnt++;
                st.pop_back();
            }
            else st.push_back(s[i]-'0');
        }
    }
    if(cnt % 2 == 0) cout << "NET" << endl;
    else cout << "DA" << endl;
}

C. Pluses and Minuses

累積和を取ると初期値がのときどこまで操作が続くかを求めることが出来る
初期値がだとするとが最初に出現する場所まで操作が続くのでその長さを加算する
文字列の末尾までたどり着けるときbreakすればいい
提出コード

void solve(){
    string s;
    cin >> s;
    int n = s.size();
    vector<int> idx(n+10, -1);
    int cur = 0;
    REP(i,n){
        if(s[i] == '-') cur--;
        else cur++;
        if(cur < 0){
            if(idx[abs(cur)] >= 0) continue;
            idx[abs(cur)] = i;
        }
    }

    ll ans = 0;
    for(int i=0;i<=n;i++){
        cur = -i - 1;
        // cout << i << " " << cur << endl;
        if(idx[abs(cur)] == -1){
            ans += n;
            break;
        }
        else ans += idx[abs(cur)] + 1;
        //cout << ans << endl;

    }
    cout << ans << endl;
}

D. Maximum Sum on Even Positions

操作を考えると区間が奇数のときは変化しないので、偶数の場合のみを考える
この時、偶数番目の要素を負として扱うと、連続区間の部分和の最大を求めればよくこれはで求めることが出来る
後は、偶数番目からスタートか奇数番目からスタートかの2通りあるのでそれぞれ求めればいい
提出コード

void solve(){
    int n;
    cin >> n;
    vector<int> a(n);
    ll sum = 0;
    REP(i,n){
        cin >> a[i];
        if(i % 2 == 0) sum += a[i];
    }
    ll cur = 0, even = INF, odd = 0;
    ll ma = 0;
    REP(i,n){
        cur += (i & 1 ? a[i] : -a[i]);
        if(i % 2 == 0){
            chmax(ma, cur - even);
            chmin(even, cur);
        }
        else{
            chmax(ma, cur - odd);
            chmin(odd, cur);
        }
    }
    cout << sum + ma << endl;
}