Codeforces Round #677 (Div. 3)

codeforces.com

A. Boring Apartments

いい方針思いつかなかったので文字列作って一致するまで足すようにした
提出コード

void solve(){
    string x;
    cin >> x;
    vector<string> S;
    for(char c='1';c<='9';c++){
        string t = "";
        t += c;
        S.emplace_back(t);
        t += c;
        S.emplace_back(t);
        t += c;
        S.emplace_back(t);
        t += c;
        S.emplace_back(t);
    }
    int ans = 0;
    int cur = 1;
    REP(i,S.size()){
        ans += cur;
        cur++;
        if(cur >= 5) cur = 1;
        if(S[i] == x) break;
    }
    cout << ans << endl;
}

B. Yet Another Bookshelf

左側の連続した0と右側の連続した0は無視できるので左右の一番初めに出てくる1の位置をl, rとすると区間の0の個数を数えればいい
提出コード

void solve(){
    int n;
    cin >> n;
    vector<int> a(n);
    REP(i,n) cin >> a[i];
    int l = 0, r = n-1;
    for(int i=0;i<n;i++){
        if(a[i] == 1){
            l = i;
            break;
        }
    }
    for(int i=r;i>=0;i--){
        if(a[i] == 1){
            r = i;
            break;
        }
    }
    int ans = 0;
    for(int i=l;i<=r;i++) if(a[i] == 0) ans++;
    cout << ans << endl;
}

C. Dominant Piranha

与えられた配列の要素が全て同じなら答えは-1になる
それ以外の場合は配列の最大の要素が初手で動けるならその要素は必ず条件を満たすのでそのような要素のindexを出力する
提出コード

void solve(){
    int n;
    cin >> n;
    vector<int> a(n);
    int mi = INF, ma = 0;
    REP(i,n){
        cin >> a[i];
        chmin(mi, a[i]);
        chmax(ma, a[i]);
    }
    if(ma == mi) cout << -1 << endl;
    else{
        REP(i,n){
            if(a[i] == ma){
                if(i > 0 and a[i-1] != ma){
                    cout << i + 1 << endl;
                    return;
                }
                if(i < n-1 and a[i+1] != ma){
                    cout << i + 1 << endl;
                    return;
                }
            }
        }
    }
}

D. Districts Connection

制約が小さいのでで各頂点同士の間に辺を張れるかどうかを確認できる
張ってもいい辺の中で全域木を作ることができれば、条件を満たすことができる
これはUnionFindを使って、頂点集合を管理しながら辺を追加していけばいい
提出コード

void solve(){
    int n;
    cin >> n;
    vector<int> a(n);
    REP(i,n) cin >> a[i];
    UnionFind uf(n);
    vector<pair<int, int>> ans;
    REP(i,n) for(int j=i+1;j<n;j++){
        if(a[i] != a[j]){
            if(uf.issame(i, j)) continue;
            ans.emplace_back(i+1, j+1);
            uf.unite(i, j);
        }
    }
    if(ans.size() < n-1) cout << "NO" << endl;
    else{
        cout << "YES" << endl;
        for(auto [x, y] : ans) cout << x << " " << y << endl;
    }
}

E. Two Round Dances

問題文が間違っていたっぽい
よくわからなかったのでエスパーしてサンプルを合わせました…
サンプルをぐっと睨むとがサンプルと一致することがわかる（？）
提出コード

void solve(){
    int n;
    cin >> n;
    ll ans = 1;
    for(ll i=1;i<n;i++) ans *= i;
    cout << ans / (n / 2) << endl;
}

F. Zero Remainder Sum

初期化ミスってるやつはhackされるっぽい
i行j列目まで見て、l個取った時のmod Kがkの時の総和の最大としてDPをする
4次元vectorはちょっと怖かったので3次元にした
提出コード

void solve(){
    int n, m, K;
    cin >> n >> m >> K;
    vector<vector<int>> a(n, vector<int>(m));
    REP(i,n) REP(j,m) cin >> a[i][j];
    vector<vector<vector<int>>> dp(m+1, vector<vector<int>>(m/2+1, vector<int>(K, -1)));
    dp[0][0][0] = 0;
    REP(i,n){
        vector<vector<vector<int>>> next(m+1, vector<vector<int>>(m/2+1, vector<int>(K,-1)));
        REP(j,m){
            REP(l,m/2){
                REP(k,K){
                    if(dp[j][l][k] == -1) continue;
                    chmax(dp[j+1][l][k], dp[j][l][k]);
                    chmax(dp[j+1][l+1][(k+a[i][j])%K], dp[j][l][k] + a[i][j]);
                }
            }
        }
        REP(j,m+1) REP(l, m/2+1) REP(k,K) chmax(next[0][0][k], dp[j][l][k]);
        swap(dp, next);
    }
    int ans = 0;
    REP(i,m/2+1) chmax(ans, dp[0][i][0]);
    cout << ans << endl;
}

G. Reducing Delivery Cost

全ての辺に対しその辺のコストを0にした時の全体のコストの総和が求められればいい
これは全頂点間のコストがわかれば、各辺に対し、その辺のコストを0にした時のコストの全体がで計算できる
全頂点間のコストは各頂点に対しダイクストラ法を使うことで求めることができる
そのため、ダイクストラ法で全頂点間のコストを求めた後、どの辺のコストを0にするかを全探索すればいい
提出コード

void solve(){
    int n, m, k;
    cin >> n >> m >> k;
    vector<int> x(m), y(m), w(m);
    Dijkstra<ll> dijk(n, LINF);
    REP(i,m){
        cin >> x[i] >> y[i] >> w[i];
        --x[i], --y[i];
        dijk.make_edge(x[i], y[i], w[i]);
        dijk.make_edge(y[i], x[i], w[i]);
    }
    vector<vector<ll>> d(n, vector<ll>(n));
    REP(i,n){
        dijk.solve(i);
        d[i] = dijk.cost;
    }
    vector<int> a(k), b(k);
    REP(i,k){
        cin >> a[i] >> b[i];
        --a[i], --b[i];
    }
    ll ans = LINF;
    REP(i,m){
        ll sum = 0;
        REP(j,k){
            ll tmp = d[a[j]][b[j]];
            chmin(tmp, d[a[j]][x[i]] + d[y[i]][b[j]]);
            chmin(tmp, d[a[j]][y[i]] + d[x[i]][b[j]]);
            sum += tmp;
        }
        chmin(ans, sum);
    }
    cout << ans << endl;
}