[AtCoder]AtCoder Beginner Contest 189 A~D問題

A問題

1文字目が２、３文字目と等しいかどうか調べる。

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

int main()
{
    string n;
    cin >> n;

    if(n[0] == n[1] && n[0] == n[2]){
        cout << "Won" << endl;
    }else{
        cout << "Lost" << endl;
    }

    return 0;
}

B問題

各iごとのアルコール量(ml)を整数で計算すると除算で誤差が発生するため、閾値(X)の方に x 100して計算する。

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

int main()
{
    int n,x;
    cin >> n >> x;
    x *= 100;

    int sum = 0;
    for(int i =0; i < n; i++){
        int v,p;
        cin >> v >> p;
        sum += v * p;
        if(x < sum){
            cout << i + 1 << endl;
            return 0;
        }
    }

    cout << -1 << endl;

    return 0;
}

C問題

※O(n^2)でも間に合うそうなので正攻法じゃないかもしれません。

1. ある範囲におけるみかんを食べられる個数は 範囲 x 範囲内の最小値で求まる
2. 1の最小値を範囲に含める限り範囲を広める以外にみかんを食べる個数を増やせない

上記のことから範囲1~Nを初期値として範囲内の最小値を境に前後で範囲を分割し二分探索法で最大値を再帰的に算出する。

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

int n;
vi a(1000000);

int solve(int l ,int r){
    if(l < 0 || l >= r || r > n) return 0;
    auto min_itr = min_element(a.begin() + l, a.begin() + r); 
    int min_index = distance(a.begin(), min_itr);
    return max(max(solve(l, min_index), solve(min_index + 1, r)), (r-l) * (*min_itr));
}

int main()
{
    cin >> n;
    for(int i = 0; i < n; i++){
        cin >> a[i];
    }

    cout << solve(0, n) << endl;

    return 0;
}

D問題

Y_iがTrueまたはFalseになる組み合わせはそれぞれ、Y_i-1がTrueまたはFalseになる組み合わせをもとに再帰的に求まる。
制約上、STLのpowではオーバーフローするので注意(※私はそれにハマってタイムアップしました)

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

vector<string> s(100);

ll pow2(ll a){
    ll ret = 1;
    for(int i = 0; i < a; i++) ret *= 2;
    return ret;
}

ll solve(bool y, ll i){
    if(i==0) 
        return 1;
    if(s[i] == "AND"){
        if(y == true)
            return solve(true, i-1);
        else
            return pow2(i+1) - solve(true, i-1);
    }
    else{
        if(y == true)
            return pow2(i+1) - solve(false, i-1);
        else
            return solve(false, i-1);
    }
}

int main()
{
    int n;
    cin >> n;

    for(int i = 0; i < n; i++){
        cin >> s[i+1];
    }

    cout << solve(true, n) << endl;

    return 0;
}