AtCoder ABC187 C++ 解法まとめ

このページの趣旨

AtCoderのABC問題について、問題の解法についてまとめたもの。
まだまだ未熟者なので、他の解法があれば知りたいのでコメントで共有していただけると嬉しいです。

A問題

問題ページ
https://atcoder.jp/contests/abc187/tasks/abc187_a

解法その１

文字列として読み込んで、各桁を数値に変換。
string型の場合、int型に変換すると表示される数値とint型の数値では異なるため、文字の'0'を基準とする必要がある。

a_01.cpp

#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0 ; i < (n) ; ++i)
using ll = long long;
using P = pair<int, int>;

int func(string s){
    int ret = 0;
    ret += s[0] - '0';
    ret += s[1] - '0';
    ret += s[2] - '0';
    return ret;
}

int main(){
    string a, b;
    cin >> a >> b;

    int ans = max(func(a), func(b));

    cout << ans << endl;
}

解法その２

数値として読み込んで、各桁だけを取り出す。
剰余算演算子(あまりを取り出す演算子)である'%'を使うことで、１の位を取り出し、10で割ることで１の位を削除する、というプロセスを繰り返すことで各桁の足し算が可能

a_02.cpp

#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0 ; i < (n) ; ++i)
using ll = long long;
using P = pair<int, int>;

int func(int s){
    int ret = 0;
    while( s > 0 ){
        ret += s % 10;
        s /= 10;
    }
    return ret;
}

int main(){
    int a, b;
    cin >> a >> b;

    int ans = max(func(a), func(b));

    cout << ans << endl;
}

B問題

解法

傾き(gradient)を計算する際には、int型の計算のところに(double)を入れないと正しく計算されないので注意

b.cpp

#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0 ; i < (n) ; ++i)
using ll = long long;
using P = pair<int, int>;

int main(){

    int n;
    cin >> n;
    vector<int> x(n), y(n);
    rep(i, n) cin >> x[i] >> y[i];

    int ans = 0;

    for(int i = 0 ; i < n ; i++){
        for(int j = i+1 ; j < n ; j++){
            double grad = (double) (y[j]-y[i])/(x[j]-x[i]);
            if( grad >= -1 && grad <= +1) ans++;
        }
    }

    cout << ans << endl;

}

C問題

解法その１：setを使った解法

c_01.cpp

#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0 ; i < (n) ; ++i)
using ll = long long;
using P = pair<int, int>;


int main(){

    int n;
    cin >> n;
    vector<string> s(n);
    set<string> sset;
    rep(i, n){
        cin >> s[i];
        sset.insert(s[i]);
    }

    rep(i, n){
        if(sset.count("!" + s[i])){
            cout << s[i] << endl;
            return 0;
        }
    }

    cout << "satisfiable" << endl;

    return 0;
}

解法その２：mapを使った解法

Point

set型

set_sample.cpp

#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0 ; i < (n) ; ++i)
using ll = long long;
using P = pair<int, int>;


int main(){

    vector<string> str{"a", "b", "c", "!a"};
    set<string> set{"a", "b", "c", "!a"};

    cout << set.size() << endl;
    rep(i, str.size()){
        cout << "!" + str[i] << endl;
        cout << set.count("!" + str[i]) << endl;
    }

}

D問題

解法その１

全く演説しない場合は、青木氏と高橋氏の得票数は、

(青木氏, 高橋氏) = \left(\sum_{N} A_i,\  0 \right)

となる。ここにおいて、もし i番目 の町で高橋氏が演説を行ったならば、得票数の変化は次のようになる。

高橋氏が得る票数 - 青木氏が失う票数 = 2\times A_i + B_i

したがって、もともとの青木氏の得票数と、演説による得票数の変化が以下のようになった場合、高橋氏が当選する。

\sum_{N} A_i < \sum_{\mathrm{ans}} (2\times A_i + B_i)

演説回数が最も少なくしたい場合は、得票数の変化量を大きい順でsortし、上から順番に計算していって、上記式を満たす回数試行することで解答が得られる。

d.cpp

#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0 ; i < (n) ; ++i)
using ll = long long;
using P = pair<int, int>;


int main(){
    int n;
    cin >> n;
    vector<ll> a(n), b(n);
    ll sa = 0;
    vector<ll> dec;
    rep(i, n) {
        cin >> a[i] >> b[i];
        sa += a[i];
        dec.push_back(2*a[i] + b[i]);
    }

    sort(dec.begin(), dec.end(), greater<ll>());

    int ans = 0;
    while( sa >= 0 ){
        sa -= dec[ans];
        ans++;
    }
    cout << ans << endl;

    return 0;
}