接着剤の精進日記

競プロでの精進や研究に関係したことを書いていきます。

Educational Codeforces Round 90 (Rated for Div. 2)

codeforces.com

A. Donut Shops

読解が辛い
 a \geq cのとき1つ目のお店のほうが小さくなる個数は存在しない
 ab \leq cのとき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

累積和を取ると初期値がiのときどこまで操作が続くかを求めることが出来る
初期値がiだとすると-i-1が最初に出現する場所まで操作が続くのでその長さを加算する
文字列の末尾までたどり着けるとき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

操作を考えると区間が奇数のときは変化しないので、偶数の場合のみを考える
この時、偶数番目の要素を負として扱うと、連続区間の部分和の最大を求めればよくこれは\mathcal{O}(n)で求めることが出来る
後は、偶数番目からスタートか奇数番目からスタートかの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;
}