Codeforces Round #674 (Div. 3)

codeforces.com

A. Floor Number

なら答えは1
そうでないなら
提出コード

void solve(){
    int n, x;
    cin >> n >> x;
    if(n <= 2) cout << 1 << endl;
    else cout << ((n - 2) + x - 1) / x + 1 << endl;
}

B. Symmetric Matrix

まずが奇数の時答えは"NO"
それ以外の時のタイルが1つでもあれば条件を満たせる
提出コード

void solve(){
    int n, m;
    cin >> n >> m;
    bool ok = false;
    REP(i,n){
        int a, b, c, d;
        cin >> a >> b >> c >> d;
        if(b == c) ok = true;
    }
    if(ok and m % 2 == 0) cout << "YES" << endl;
    else cout << "NO" << endl;
}

C. Increase and Copy

操作を考えると最初の要素をある数字まで増やしてその後コピーするのが効率がいい
これを愚直に調べると最大ケースでも大体くらいで答えが最小になることがわかる
そのため、の範囲で個まで要素をコピーする時の最小の値を全探索すればいい
提出コード

void solve(){
    int n;
    cin >> n;
    ll ans = n-1;

    for(int i=1;i*i<=n;i++){
        ll cnt = (n + i - 1) / i;
        ll tmp = cnt - 1 + i - 1;
        chmin(ans, tmp);
    }
    cout << ans << endl;
}

D. Non-zero Segments

基本的にはZero-Sum Rangesのような感じ
mapなどで累積和を保存していってすでに出た値があればその区間の総和は0になる
この問題の場合、その区間があったら今見ている値の一個前にクソデカ定数を適当に入れればこれ以前の区間で総和が0になるものはなくなる
そのため、総和が0になる区間が見つかれば、答えを加算しmapを初期化する
提出コード

void solve(){
    int n;
    cin >> n;
    vector<ll> a(n);
    REP(i,n) cin >> a[i];
    map<ll, int> mp;
    ll sum = 0;
    mp[sum]++;
    ll ans = 0;
    REP(i,n){
        sum += a[i];
        if(mp[sum] > 0){
            ans++;
            mp = map<ll, int>();
            sum = a[i];
            mp[0]++;
        }
        mp[sum]++;
    }
    cout << ans << endl;
}

E. Rock, Paper, Scissors

まず勝てる最大を考える
自分がグーで相手がチョキのとき勝てる最大は双方の小さい方となる
そのため、同様に自分がチョキとパーの場合の最大を求めてその和が答え
次に、最小の場合を考える
自分がグーを出すときできるだけあいこと負けで消費をする必要がある
自分のグーから相手のグーとパーを引いて値が正ならその残りは相手のチョキと戦って勝つことになる
aを自分の手、bを相手の手、グーチョキパーを0,1,2とする
そうするとの最小値が答えとなる
フロー流してもいいらしい
提出コード

void solve(){
    int n;
    cin >> n;
    vector<int> a(3), b(3);
    REP(i,3) cin >> a[i];
    REP(i,3) cin >> b[i];
    int mi = 0, ma = 0;
    ma = min(a[0], b[1]) + min(a[1], b[2]) + min(a[2], b[0]);
    REP(i,3){
        chmax(mi, max(0, a[i] - b[i] - b[(i-1+3)%3]));
    }
    cout << mi << " " << ma << endl;
}

提出コード（フロー）

void solve(){
    int n;
    cin >> n;
    vector<int> a(3), b(3);
    REP(i,3) cin >> a[i];
    REP(i,3) cin >> b[i];
    int s = 6, t = 7;
    Dinic<ll> g(8);
    REP(i,3) g.add_edge(s, i, a[i]);
    REP(i,3) g.add_edge(i+3, t, b[i]);
    REP(i,3) REP(j,3) if((i + 1) % 3 != j){
        g.add_edge(i, 3+j, INF);
    }
    ll ma = min(a[0], b[1]) + min(a[1], b[2]) + min(a[2], b[0]);
    ll mi = n - g.flow(s,t);
    cout << mi << " " << ma << endl;
}

F. Number of Subsequences

AtCoderで既出
"a"、"ab"、"abc"が幾つ作れるかをdpで数えていけばいい
atcoder.jp

提出コード

void solve(){
    int n;
    string s;
    cin >> n >> s;
    vector<vector<mint>> dp(n+10, vector<mint>(5));
    dp[0][0] = 1;
    REP(i,n){
        REP(j,5){
            if(s[i] == '?') dp[i+1][j] += dp[i][j] * 3;
            else dp[i+1][j] += dp[i][j];
        }
        if(s[i] == 'a' or s[i] == '?') dp[i+1][1] += dp[i][0];
        if(s[i] == 'b' or s[i] == '?') dp[i+1][2] += dp[i][1];
        if(s[i] == 'c' or s[i] == '?') dp[i+1][3] += dp[i][2];
    }
    cout << dp[n][3] << endl;
}