NOMURA プログラミングコンテスト 2020

atcoder.jp

競プロなんもわかんね〜

滑　り　台　笑
Bondo416さんのNOMURA プログラミングコンテスト 2020での成績：4128位
パフォーマンス：481相当
レーティング：1304→1243 (-61) :(#AtCoder https://t.co/LFn81M23os pic.twitter.com/bdVsJhPvYX

— ボンド@競プロ (@bond_cmprog) 2020年5月30日

A - Study Scheduling

分に直してから計算する
提出コード

void solve(){
    int H1, M1, H2, M2, K;
    cin >> H1 >> M1 >> H2 >> M2 >> K;
    ll sum = H2 * 60 + M2 - (H1 * 60 + M1);
    cout << sum - K << endl;
}

B - Postdocs

ぱっと見わかんなくてDP書いて思いとどまった
'?'に’D'を置くのが最適になる
提出コード

void solve(){
    string T;
    cin >> T;
    REP(i,(int)T.size()){
        if(T[i] == '?') T[i] = 'D';
    }
    cout << T << endl;
}

C - Folia

解ける人多くて困った
葉から考えて深さdのときに頂点として選べる最小と最大の区間を求める
その後、上から取れる最大と求めた区間の範囲との最大を貪欲に取っていけばいい
もしくは、最初から上から見ていくとする
深さdを見ている時、その頂点数の最大は深さd-1の葉を除いた頂点数の2倍まで最大で取れる
また、深さdの葉ではない頂点は深さd+1以降で葉となる頂点が存在するため、以下を満たす
この2つの条件を満たす範囲のうち最大のものを貪欲に取っていけばいい
提出コード

void solve(){
    int N;
    cin >> N;
    vector<ll> A(N+1), cum(N+1);
    REP(i,N+1) cin >> A[i];
    cum[0] = A[0];
    for(int i=1;i<=N;i++) cum[i] = cum[i-1] + A[i];

    if(N == 0 && A[0] == 1){
        cout << 1 << endl;
        return;
    }
    if(A[0] != 0){
        cout << -1 << endl;
        return;
    }

    ll cur = 1, ans = 0;
    REP(i,N+1){
        // cout << i << " " << cur << endl;
        if(cur - A[i] < 0){
            cout << -1 << endl;
            return;
        }
        ans += cur;
        cur -= A[i];
        if(cur > cum[N] - cum[i]){
            cout << -1 << endl;
            return;
        }
        cur = min(cur * 2, cum[N] - cum[i]);
    }
    cout << ans << endl;
}