AtCoder Beginner Contest 159 参加記

ABC159に参加しました。 Eの無限ループに気づかず4完でした。悲しいです。実装は自分なりに綺麗にできていたのでそこは満足しています。

A - The Number of Even Pairs

問題へのリンク

偶数が $N$ 個、奇数が $M$ 個から $2$ つ選んで足して偶数になるペアは何通りあるか数える問題。

$_{N}C_{2} + _{M}C_{2}$ でよいです。

B - String Palindrome

問題へのリンク

奇数長の文字列Sが

全体で回文
前半の文字列が回文
後半の文字列が回文

の $3$ つの条件を満たすか判定する問題。回文判定はstring(s.rbegin(), s.rend()を使うと楽にできるらしいですね。

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

bool pal(string s){
    return s == string(s.rbegin(), s.rend());
}
int main() {

    string S;
    cin >> S;
    int N = S.size();
    if(pal(S) && pal(S.substr(0, (N-1)/2)) && pal(S.substr((N+3)/2-1))){
        cout << "Yes" << endl;
    }
    else{
        cout << "No" << endl;
    }
}

C - Maximum Volume

問題へのリンク

三辺の和が $L$ の長方形の体積の最大値を出力してくださいという問題。

結論的には三等分するのがよいです。解説は相加平均相乗平均の関係を使っていました。本番は無限人が通していたのでこれだろうというエスパーをしました・・・。どの辺に対しても体積は対象なのでどれかを大きくしたらいいとかはなさそうというのは直感としてありますが。

不動小数点に関して気をつけましょう。cout << fixed << setprecision(20);というおまじないをつけるといいです。

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    cout << fixed << setprecision(20);

    long double L;
    cin >> L;
    cout << (L * L * L) / 27.0 << endl;
}

D - Banned K

問題へのリンク

数字がたくさんあり、同じ数字同士のペアが何通りあるかを数える。 $k$ 番目を取り除いたときの組み合わせの値を求める問題。

$k$ 番目が消えたときに何が消えるかといえば、k番目と他の同じ値とのペアの個数なので、それを都度合計から引けばいいです。実装はmapを使っていますが、普通に配列に保存するのでいいと思います。

こういうある値を除いたときのスコアみたいなやつは、全部あるとみなして、何が差分として生じるかを考えるといいです。

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    cout << fixed << setprecision(20);

    int N; 
    cin >> N;
    vector<ll> A(N);
    map<ll, ll> mp;
    rep(i,N){
        cin>>A[i];
        mp[A[i]]++;
    }
    map<ll, ll> ans;
    for(auto p:mp){
        ans[p.first] = p.second * (p.second-1) / 2;
    }
    ll res = 0;
    for(auto p:ans){
        res +=p.second;
    }
    rep(i,N){
        ll anss = res - (mp[A[i]] - 1);
        cout << anss << endl;
    }
}