Codeforces Round #645 (Div. 2)

codeforces.com

A. Park Lighting

を出力
提出コード

void solve(){
    int n, m;
    cin >> n >> m;
    cout << (n * m + 1) / 2 << endl;
}

B. Maria Breaks the Self-isolation

ソートをし、小さい方からシミュレートをする
提出コード

void solve(){
    int n;
    cin >> n;
    vector<int> a(n);
    REP(i,n) cin >> a[i];
    sort(a.begin(), a.end());
    int cur = 1;
    int num = 1;
    REP(i,n){
        if(cur + num - 1 >= a[i]){
            cur += num;
            num = 1;
        }
        else{
            num++;
        }
    }
    cout << cur << endl;
}

C. Celex Update

editorialの図がわかりやすかった

和が最小の経路を基準にし、最大の経路まで何通りあるかを考える
そうすると図のように通りあることがわかる
よって、これに最小の経路を加算したものが答え
多倍長とか使えば最小と最大の間は全部作れるいつものあれかな
提出コード

void solve(){
    ll x1, x2, y1, y2;
    cin >> x1 >> y1 >> x2 >> y2;
    ll dx = x2 - x1;
    ll dy = y2 - y1;
    cout << dx * dy + 1 << endl;
}

D. The Best Vacation

各月の和でしゃくとりをする
この和がxに足りないときは、余った分を加えてあげればいい
年度を跨いでもいいので、2周分取っておくと楽
提出コード

void solve(){
    ll n, x;
    cin >> n >> x;
    vector<ll> d(2*n);
    REP(i,n){
        cin >> d[i];
        d[i+n] = d[i];
    }
    int right = 0;
    ll sum = 0;
    ll sumDays = 0;
    ll ans = 0;
    for(int left=0;left<n;left++){
        while(right < 2*n && sumDays + d[right] <= x){
            sum += d[right] * (d[right] + 1) / 2;
            sumDays += d[right];
            right++;
        }
        ll rem = x - sumDays;
        ll tmp = sum;
        if(rem > 0) tmp += rem * (d[right] + d[right] - rem + 1) / 2;
        chmax(ans, tmp);
        if(left == right) right++;
        else{
            sum -= d[left] * (d[left] + 1) / 2;
            sumDays -= d[left];
        }
    }
    cout << ans << endl;
}