ABC D - Maximum Average Sets

#include <iostream>
#include <vector>
#include <cmath>
#include <algorithm>
#include <iomanip>

typedef long long ll;
using namespace std;
int main() {
    int n, a, b;
    cin >> n >> a >> b;
    vector<ll> v(n);
    for(int i=0;i<n;i++) {
        cin >> v[i];
    }
    sort(v.begin(), v.end(), greater<ll>());

    int max_cnt = 0;
    int cnt_a = 0, idx_a;
    for(int i=0;i<n;i++) {
        if(v[0] == v[i]) max_cnt++;
    }
    for(int i=0;i<n;i++) {
        if(v[i] == v[a-1]) {
            cnt_a++;
            idx_a = i;
        }
    }
    idx_a++;

    ll dp[55][55];
    dp[0][0] = 1;
    ll ans = 0;
    for(int i=1;i<=50;i++) {
        for(int j=0;j<=50;j++) {
            if(i>0 && j>0) 
                dp[i][j] = dp[i-1][j] + dp[i-1][j-1];
            else 
                dp[i][j] = dp[i-1][j];
        }
    }
    if(max_cnt > a) {
        int lim = min(max_cnt, b);
        for(int i=a;i<=lim;i++) {
            ans += dp[max_cnt][i];
        }
    } else {
        int lim = idx_a - cnt_a;
        ans += dp[cnt_a][a-lim];
    }

    double ave = 0;
    for(int i=0;i<a;i++) {
        ave += v[i];
    }

    cout << fixed << setprecision(6) << ave * 1.0 / a << endl;
    cout << ans << endl;

}

Codeforces #405 C. Bear and Different Names

  • 方針
    まず、n個の異なる名前を用意。 i番目が"NO"なら、ans[i+k-1] = ans[i]とするとi番目以外のk個のグループには影響がない。
    ここで、ans[i] = ans[i+k-1]とすると、ans[i+k-1]が後から更新された場合にこまる。

自分の回答

#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
using namespace std;

typedef long long ll;

int main() {
    int n, k;
    cin >> n >> k;
    vector<string> ans(n);
    int cnt = 0;
    char suff = 'A', name = 'a';
    for(int i=0;i<n;i++) {
        if(cnt > 25) {
            suff++;
            name = 'a';
        }
        string a{suff}, b{name};
        //ans[i] = suff + (char) name;
        ans[i] = a + b;
        //cout << suff + name << endl;
        cnt++;
        name++;
    }
    for(int i=0;i<n-k+1;i++) {
        string si;
        cin >> si;
        if(si == "NO") {
            ans[i+k-1] = ans[i];
        }
    }
    for(int i=0;i<n;i++) {
        cout << ans[i] << " ";
    }
    cout << endl;
}

模範解答

#include <bits/stdc++.h>
using namespace std;
string s[105];
int main() {
    int n, k;
    cin >> n >> k;
    // generate n different names
    for(int i = 1; i <= n; ++i) {
        s[i] = "Aa";
        s[i][0] += i / 26;
        s[i][1] += i % 26;
    }
    for(int start = 1; start <= n - k + 1; ++start) {
        string should;
        cin >> should;
        if(should[0] == 'N') // not effective group
            s[start+k-1] = s[start]; // make two names equal
    }
    for(int i = 1; i <= n; ++i) cout << s[i] << " ";
    cout << "\n";
}

Codeforces #405 B. Bear and Friendship Condition

  • 方針
    グラフ中の全ての部分グラフ?で
    (辺の数)= (頂点の数)*(頂点の数-1) / 2
    を満たしていれば “YES"、そうでなければ "NO"と出力。
    全探索するために配列 vis[頂点の数] を用意。 dfsでは一つの辺に対して二回ずつカウントしている。 つまり、cnt_eには本来の辺の二倍の数が格納されることになる。
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

vector<bool> vis(150010, false);
vector<ll> g[150010];
void dfs(int a, int & cnt_v, int & cnt_e) {
    if(vis[a]) return;
    vis[a] = true;
    cnt_v++;
    cnt_e += g[a].size();

    for(int i=0;i<g[a].size();i++) {
        if(!vis[g[a][i]]) {
            dfs(g[a][i], cnt_v, cnt_e);
        }
    }
}

int main() {
    ll n, m;
    cin >> n >> m;
    for(int i=0;i<m;i++) {
        int ai, bi;
        cin >> ai >> bi;
        ai--; bi--;
        g[ai].push_back(bi);
        g[bi].push_back(ai);
    }

    for(int i=0;i<n;i++) {
        if(!vis[i]) {
            int cnt_v = 0, cnt_e = 0;
            dfs(i, cnt_v, cnt_e);
            if(cnt_e != (ll) cnt_v * (cnt_v - 1)) {
                cout << "NO" << endl;
                //cout << cnt_e << " "<< cnt_v << endl;
                return 0;
            }
        }
    }
    cout << "YES" << endl;
}

Codeforces #403 C. Andryusha and Colored Balloons

  • 方針
    解けなかったので他の人の解答をみた。
#include <iostream>
#include <vector>
#include <set>
using namespace std;

set<int> c[200010];
vector<int> g[200010], p(200010, 0), a(200010, 0);

void dfs(int cur, int pre) {
    if(pre != -1) {
        while(c[pre].count(p[pre])) p[pre]++;
        a[cur] = p[pre];
        c[pre].insert(a[cur]);
        c[cur].insert(a[pre]);
    }
    c[cur].insert(a[cur]);
    for(int i=0;i<g[cur].size();i++) {
        if(g[cur][i] != pre) {
            dfs(g[cur][i], cur);
        }
    }

}

int main() {
    int n;
    cin >> n;
    for(int i=0;i<n-1;i++) {
        int a, b;
        cin >> a >> b;
        a--; b--;
        g[a].push_back(b);
        g[b].push_back(a);
    }
    dfs(0, -1);
    int ans = 0;
    for(int i=0;i<n;i++) {
        ans = max(ans, a[i]); 
    }
    cout << ans + 1 << endl;
    for(int i=0;i<n;i++) {
        cout << a[i] + 1 << " ";
    }
    cout << endl;

}

AGC011_B Colorful Creatures

  • 方針
    昇順にソートして、それぞれの累積和を計算しておく。すると、i番目の生き物が他のすべての生き物と合体するためには、0<=i<=n-2について(0から始まるインデックス基準)、(i番目の累積和)*2 >= (i+1番目の生物の大きさ)を満たしている必要がある。逆に言うと、これを満たさない生物iがあった場合、それ以下の生物も同様に条件をみたすことができない。
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

typedef long long ll;

int main() {
    ll n;
    cin >> n;
    vector<ll> a(n);
    for(int i=0;i<n;i++) cin >> a[i];
    sort(a.begin(), a.end());
    vector<ll> sum(n);
    for(int i=0;i<n;i++) {
        if(i==0) sum[i] = a[i];
        else {
            sum[i] = sum[i-1] + a[i];
        }
    }
    int ans=n;
    for(int i = n-2;i>=0;i--) {
        if(sum[i] * 2 < a[i+1]) {
            ans -= (i + 1);
            break;
        }
    }
    cout << ans << endl;

}

AGC011_A Airport Bus

  • 方針
    やるだけなのにやけに時間がかかった。自分はアルゴリズム云々の前に、こういう基本的なプログラムの挙動に対する直感がかけているのかも?
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
typedef long long ll;

int main() {
    ll n, c, k;
    cin >> n >> c >> k;
    vector<ll> t(n);
    for(int i=0;i<n;i++) cin >> t[i];
    sort(t.begin(), t.end());

    int j = 0, ans = 1;
    for(int i=0;i<n;i++) {
        if(t[i] > t[j] + k || i == j + c) {
            ans++;
            j = i;
        }
    }
    cout << ans << endl;
}

Codeforces #401 C. Alyona and Spreadsheet

  • 概要
    n ✕ mの整数テーブルが与えられる。加えて整数kとk個のl[i],r[i]が与えられる。 テーブルのうち、l[i]からr[i]が単調増加(a[i][j] <= a[i][j+1])ならYes, そうでなければNoを出力する。

  • 方針 a[i][j] <= a[i+1][j] かつi<n-1のとき dp[i] = dp[i+1] + 1 それ以外のとき dp[i] = 1 とする。 列ごとにdp[i]を作成し、ans[i] = max(ans[i], dp[i])とする。 l[i] - r[i] +1 <= ans[l[i]-1] のときYes, そうでないときNoを出力

#include <iostream>
#include <vector>
using namespace std;

typedef long long ll;

int main() {
    int n, m;
    cin >> n >> m;
    ll a[n][m];
    for(int i=0;i<n;i++) {
        for(int j=0;j<m;j++) {
            cin >> a[i][j];
        }
    }
    vector<int> ans(n, 0);
    for(int i=0;i<m;i++) {
        vector<ll> v(n);
        for(int j=n-1;j>=0;j--) {
            if(j == n-1)
                v[j] = 1;
            else if(a[j][i] > a[j+1][i])
                v[j] = 1;
            else
                v[j] = v[j+1] + 1;
            ans[j] = max<ll>(ans[j], v[j]);
        }
    }

    int k;
    cin >> k;
    for(int i=0;i<k;i++) {
        int l, r;
        cin >> l >> r;
        if(ans[l-1] >= r - l + 1)
            cout << "Yes" << endl;
        else
            cout << "No" << endl;
    }
}