Educational Codeforces Round 86 (Rated for Div. 2) 参加記

コンテストへのリンク

参加しました。結果は以下です。

A - Road To Zero

問題概要

を

• するのに＄かかる
• するのに＄かかる。

両方の状態にするのにかかる最小費用を求めよ。

解説

減らす操作以外無駄である。両方同じになるまで減らして、同時に減らしていくか、独立に減らしていくかの最小値。

void solve(){
    ll x, y, a, b;
    cin >> x >> y;
    cin >> a >> b;
    ll ans = 0;
    ans += a * abs(x-y);
    ans += min(x, y) * b;

    ll ans2 = 0;
    ans2 += a*(x+y);
    cout << min(ans,ans2) << endl;
}

B - Binary Period

問題概要

文字列が与えられる。以下の条件を満たす文字列をつ求めよ。

1. はとのみで構成される。
2. 
3. はの部分列である（連続である必要はない）
4. は、1. ~ 3.を満たす文字列の中で、最小の長さの周期を持つ。

解説

まず、のもじが全部同じならそれ自体が長さ1の周期を持つ文字列で、条件を満たす。

一つでも違う場合だが、周期をにしながら、を満たす文字列が存在するので、それを構築して出力すればよい。

void solve(){
    string t;
    cin >> t;
    int N = t.size();
    int cnt = 0;
    rep(i,N)cnt += (t[i] == '1');
    if(cnt == 0 || cnt == N){
        cout << t << endl;
        return;
    }
    rep(i,N){
        if(t[i] == t[i+1]){
            if(t[i] == '1'){
                cout << "10";
            }
            else{
                cout << "01";
            }
        }
        else{
            cout << t[i];
        }
    }
    cout << endl;
}

C - Yet Another Counting Problem

問題概要

2つの整数が与えられる。 で、となるの個数を求めよ。 クエリは回ある。

解説

で割った余りに関する値は、との最小公倍数をとすれば、の周期で表れる。よって、一度に関する値を求めておいて、それが何回繰り返すのか、余りがいくらなのかによって調整すればよい。よくある周期の問題である。

ll lcm(ll a,ll b){return a/gcd(a,b)*b;}

void solve(){
    ll a, b, q;
    cin >> a >> b >> q;
    ll L = lcm(a, b);
    //[0,L)の1周期にある数
    vector<ll> cnt(L+1, 0);
    cnt[0] = 0;
    rep(i,L){
        cnt[i+1] = cnt[i]+(((i%a)%b != (i%b)%a));
    }
    auto f = [&](ll X){
        //[0, L) * 数
        ll res = cnt[L] * (X / L);
        //[0, X%L]
        res += cnt[X%L+1];
        return res;
    };
    while(q--){
        ll l, r;
        cin >> l >> r;
        cout << f(r) - f(l-1) << " ";;
    }
    cout << endl;
}

D - Multiple Testcases

問題概要

まだ掴めてません・・・・Readforcesさん・・・・