Codeforces Round #540 (Div. 3)

A - Water Buying

https://codeforces.com/contest/1118/problem/A

方針

1 リットルのボトル 2 つの値段が 2 リットルボトル以下のとき ()、 リットルすべてを 1 リットルのボトルで買えばよく、答えは です。

それ以外のとき、2 リットルボトルをできるだけ多く買い、最後に 1 リットル不足すれば 1 リットルボトルを買えばよいです。答えは です。

ソースコード

#include <bits/stdc++.h>
#define ll long long
using namespace std;

int main(){
    int q;  cin >> q;
    while(q > 0){
        ll n, a, b;  cin >> n >> a >> b;
        if(2*a <= b) cout << n*a << endl;
        else cout << n/2*b + (n%2)*a <<endl;
        q--;
    }
}

B - Tanya and Candies

https://codeforces.com/contest/1118/problem/B

方針

アメ を父親にあげたとすると、アメ を偶数日目に食べる条件は以下です

• のとき、 が偶数
• のとき、 が奇数

アメ を奇数日目に食べる条件は、この偶奇を逆にしたものになります。

アメ 1～ のうち偶数番目のアメの重さの和 、奇数番目のアメの重さの和 をあらかじめ計算しておきます。すなわち、

とします。

これを用いると、アメ を父親にあげるときに

• 偶数日目に食べるアメの重さの和
• 奇数日目に食べるアメの重さの和

と書け、これらが一致するような の数が求める値です。

ソースコード

#include <bits/stdc++.h>
#define ll long long
using namespace std;

int main(){
    int n;  cin >> n;
    vector<ll> a(n+1);
    for(int i=1; i<=n; i++) cin >> a[i];

    vector<ll> even(n+1,0), odd(n+1,0);
    for(int i=1; i<=n; i++){
        if(i%2==0){
            even[i] = even[i-1] + a[i];
            odd[i] = odd[i-1];
        }else{
            even[i] = even[i-1];
            odd[i] = odd[i-1] + a[i];
        }
    }

    int ans = 0;
    for(int i=1; i<=n; i++){
        ll sumEven = even[i-1] + (odd[n] - odd[i]);
        ll sumOdd = odd[i-1] + (even[n] - even[i]);
        if(sumEven==sumOdd) ans++;
    }
    cout << ans << endl;
}

C - Palindromic Matrix

https://codeforces.com/contest/1118/problem/C
コンテスト中は延々とこの問題でバグ取りをしていました。

方針

が偶数のとき
が奇数のとき

D. Coffee and Coursework

https://codeforces.com/contest/1118/problem/D2
D1 と D2 の違いは制約だけなので、まとめます。

方針

は 0 - indexed とします。
一日に飲むコーヒーが 1 杯だけのとき、全てのカフェインをCourseworkを解くエネルギーに変えることができます。よってカフェインの総量がCourseworkのページ数以下のとき、すなわち
　　
のとき、Courseworkを終えることは不可能なので -1 を出力します。

そうでないとき、必ずCourseworkを終えられるようなコーヒーの飲み方が存在します。求める最短日数は 1 日以上 n 日以下で、これを二分探索で求めます。

そこで、k 日で終えられるか否かを判定することが出来ればよいです。
1 日に何杯もコーヒーを飲むことによる損失を出来るだけ抑えたいので、1 日あたりの杯数を k 日間で平準化したいです。
また、コーヒーから得られるエネルギーが負になることはないので、カフェインの少ないコーヒーを 1 日の中でできるだけ後に飲むほうが得になります (たとえば、10杯目のコーヒーのカフェインが 20 の場合、得られるエネルギーは 9 減って 11 となりますが、10杯目にカフェイン 5 のコーヒーを飲めば、得られるエネルギーは 0 となり、損失は 5 に抑えられます)。

よって、k 日間でコーヒーを分配するときの最もエネルギー効率のいい分け方は、

• 1 ~ k 日目の 1 杯目は、カフェインが 1 ～ k 番目に多いコーヒー
• 1 ~ k 日目の 2 杯目は、カフェインが k+1～ 2k 番目に多いコーヒー
• 1 ~ k 日目の 3 杯目は、カフェインが 2k+1～ 3k 番目に多いコーヒー
• (以下同様)

であることがわかります。これでCourseworkを終えられるならOK、無理ならNGです。なお、 を降順にソートしておくことで、1 杯目のカフェインは 、2杯目は などと求められ、一般に は 日目に飲む 杯目のコーヒーとなります。このコーヒーで得られるエネルギーは ページ分です。

ソースコード

#include <bits/stdc++.h>
#define ll long long
using namespace std;

int main(){
    int n, m;  cin >> n >> m;
    vector<ll> a(n);
    ll sum = 0;
    for(int i=0; i<n; i++){
        cin >> a[i];
        sum += a[i];
    }
    // カフェインの総量 < ページ数 のとき、不可
    if(sum < m){
        cout << -1 << endl;
        return 0;
    }

    sort(a.begin(), a.end(), greater<ll>());
    int lday = 0, rday = n;
    while(rday - lday > 1){
        // mday 日で終えられるか否かを判定
        int mday = lday + (rday - lday)/2;
        ll sumE = 0;  // 得られるエネルギーの合計
        for(int i=0; i<n; i++){
            sumE += max(a[i]-i/mday,(ll)0);
        }
        // エネルギー総量 >= m なら OK
        if(sumE>=m) rday = mday;
        else lday = mday;
    }
    cout << rday << endl;
}

E - Yet Another Ball Problem

https://codeforces.com/contest/1118/problem/E
Ball には「舞踏会」という意味もあるんですね。

方針

k 種類の色から異なる 2 色を男女に割り当てる場合の数は 通りあります。n ペア作る必要があるので、 のときは題意を満たす色の割り振りは不可能です。NO を出力します。

のとき、必ず題意を満たす色の割り振り方があります。以下の並びを考えます：
(1, 2),(2, 1),(1, 3),(3, 1), …… (1, k),(k, 1),　(2, 3),(3, 2), …… ,(2, k),(k, 2),　(3, 4),(4, 3),…… (3, k),(k, 3),　(4, 5), …… (k-1, k), (k, k-1)
この並びは 2 色の割り当て方の全通りを網羅しており、かつ題意を満たします。よってこの並びの前から n 個を順に出力すればよいです。

ソースコード

#include <bits/stdc++.h>
#define ll long long
using namespace std;

int main(){
    ll n, k;
    cin >> n >> k;
    
    if(k*(k-1)<n){
        cout << "NO" << endl;
        return 0;
    }

    cout << "YES" << endl;
    for(ll b=1; b<=k-1; b++){
        for(ll g=b+1; g<=k; g++){
            cout << b << " " << g << endl;
            n--;
            if(n==0) return 0;

            cout << g << " " << b << endl;
            n--;
            if(n==0) return 0;
        }
    }
}