接着剤の精進日記

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

AtCoder DISCO presents ディスカバリーチャンネル コードコンテスト2020 予選

3完3ペナでパフォ1230で冷えなかったけど悔しい
Dが微妙に詰めきれてなかったのが残念

A - DDCC Finals

if文で頑張る
if文ごとに出力すると面倒なので、ansに足していくと楽かな?
提出コード

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    int X, Y;
    cin >> X >> Y;
    int ans = 0;
    if(X == 1) ans += 300000;
    if(X == 2) ans += 200000;
    if(X == 3) ans += 100000;
    if(Y == 1) ans += 300000;
    if(Y == 2) ans += 200000;
    if(Y == 3) ans += 100000;
    if(X == 1 && Y == 1) ans+= 400000;
    cout << ans << endl;
}

B - Iron Bar Cutting

これちょっと難しい
まずはどこで区切るかを全探索することを考える
そうすると区切るところの前後の長さの絶対値の差が答えになる
予め累積和で求めておいて、sumから引くとその区間で区切ったときの前後の長さが求められる
提出コード

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    int N;
    cin >> N;
    vector<ll> a(N);
    vector<ll> cum(N);
    ll sum = 0;
    REP(i,N){
        cin >> a[i];
        sum += a[i];
    }
    cum[0] = a[0];
    for(int i=1;i<N;i++) cum[i] = cum[i-1] + a[i];
    ll ans = LINF;

    REP(i,N){
        ll tmp = cum[i];
        ll rest = sum - cum[i];
        chmin(ans,abs(tmp-rest));
    }
    cout << ans << endl;
}

C - Strawberry Cakes

構築苦手なのでやめて
考えたこととして、全部の行にいちごがあれば条件を満たすように横に伸ばせば大丈夫そう
次に、いちごが無い行を考えると、いちごがある行からそのまま持ってくれば長方形を維持したまま条件を満たせる
なので、まずは横に長方形を作って、後はいちごが無い行だけ上から下にコピーして、下から上にもコピーする
提出コード

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    int H, W, K;
    cin >> H >> W >> K;
    vector<string> fi(H);
    REP(i,H) cin >> fi[i];
    vector<vector<int>> ans(H,vector<int>(W));
    vector<int> gyou(H);
    REP(i,H) REP(j,W){
        if(fi[i][j] == '#') gyou[i]++;
    }
    int cnt = 1;
    REP(i,H){
        if(gyou[i] == 0) continue;
        int tmp = 1;
        REP(j,W){
            if(fi[i][j] == '#'){
                if(tmp == 1) tmp++;
                else{
                    cnt++;
                }
            }
            ans[i][j] = cnt;
        }
        cnt++;
    }

    REP(i,H){
        if(gyou[i] > 0) continue;
        if(i == 0) REP(j,W) ans[i][j] = ans[i+1][j];
        else REP(j,W) ans[i][j] = ans[i-1][j];
    }
    for(int i=H-1;i>=0;i--){
        if(gyou[i] > 0) continue;
        if(i == H-1) REP(j,W) ans[i][j] = ans[i-1][j];
        else REP(j,W) ans[i][j] = ans[i+1][j];
    }
    REP(i,H){
        REP(j,W) cout << ans[i][j] << " ";
        cout << endl;
    }
}

D - Digit Sum Replace

これ通せなかったの悔しいな〜
本番中考えたことは、まず数字の順番によらず、開催できる回数は一定になる
シミュレーションを考えると、1回行うと桁数は1ずつ減っていき、最後は1桁残るので(全体の桁数 - 1)は操作できる
次に各桁の総和は一定になり、10以上になると1回操作出来るのでsum / 10加算するみたいに考えてた
操作に注目すると繰り上がりが無いときは各桁の総和は変わらず、逆に繰り上がる時は総和が9減る(ここ天才)ことがわかるので(sum - 1) / 9回行える
したがって、全体の回数として、(全体の桁数 - 1) + (sum - 1) / 9が答えになる
提出コード

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    int M;
    cin >> M;
    ll sum = 0;
    ll C = 0;
    ll ans = 0;

    REP(i,M){
        ll d, c;
        cin >> d >> c;
        sum += d * c;
        C += c;
    }
    ans += C - 1;
    ans += (sum - 1) / 9;
    cout << ans << endl;
}

おわりに

D大体詰めれてたんだけど、もう少し全体の性質に目が行かなかったのは反省
ダブリングとかでも通せるらしいので、そっちも確認しておきたいね
CもよくわからないWA出したの反省、企業コン苦手だ〜