[AtCoder]AtCoder Beginner Contest 128

はじめに

• AtCoder Beginner Contestの過去問の解法及び提出したソースコードをまとめています。
• 基本的に自分が振り返ることを目的としておりますが、誤りや気になった点、その他質問等もお待ちしておりますので遠慮なくお願いします。

コンテストページ

A問題

題意通りに計算するだけです。整数を2で割ったときは切り捨てですが、端数の2個未満のかけらではアップルパイは作れないので問題ありません。

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

int main()
{
    int a,p;
    cin >> a >> p;
    
    cout << (p+a*3)/2 << endl;
    return 0;
}

B問題

各レストランの番号、市名、点数を格納する構造体を定義し配列に入れた後、与えられた条件通りにソートしてあげればよいです。

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

struct Store{
    int id,p;
    string s;
};

int main()
{
    int n;
    cin >> n;
    vector<Store> stores(n);

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

    sort(stores.begin(), stores.end(), [](const Store& a, const Store& b){
        if(a.s == b.s){
            return a.p > b.p;
        }
        else {
            return a.s < b.s;
        }
    });

    for(auto& store : stores){
        cout << store.id << endl;
    }
    return 0;
}

C問題

スイッチのON/OFF状態をbit全探索で全ての組み合わせを試してあげればよいです。

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

int main()
{
    int n,m;
    cin >> n >> m;
    vector<vector<int>> s(m);
    vector<int> p(m);

    for(int i = 0; i < m; i++){
        int k;
        cin >> k;
        s[i].resize(k);
        for(int j = 0; j < k; j++){
            cin >> s[i][j];
            s[i][j]--;
        }
    }

    for(int i = 0; i < m; i++){
        cin >> p[i];
    }

    int ans = 0;
    for(int i = 0; i < (1<<n); i++){
        bitset<32> bs(i);
        bool ok = true;
        for(int j = 0; j < m; j++){
            int count = 0;
            for(auto sd : s[j]){
                count += bs[sd];
            }
            ok &= count%2==p[j];
        }
        ans += (int)ok;
    }

    cout << ans << endl;
    return 0;
}

D問題

宝石を筒に戻してから再度宝石を取り出す意味はありません。
つまりまず左側から一定個数(Aとする)、右側から一定個数(Bとする)を取り出して、その後に不要な宝石を捨てていけばよいです。
具体的には以下の手順を存在しうるA,Bの組み合わせ分全探索し、手持ちの宝石の価値の合計がもっとも大きくなるものを見つけます。

1. 左端からA個取り出す。
2. 右側からB個取り出す。
3. 持っている宝石を価値の低い順に(K-A-B)個まで捨てる。(ただし価値が1以上のものは捨てない)
4. 手持ちの合計を求める

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

int main()
{
    int n,k;
    cin >> n >> k;
    vector<int> v(n);

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

    int ans = 0;
    for(int a = 0; a <= min(k,n); a++){
        for(int b = 0; b <= min(k,n) - a; b++){
            vector<int> mine;
            for(auto itr = v.begin(); itr != v.begin() + a; itr++){
                mine.push_back(*itr);
            }
            for(auto itr = v.rbegin(); itr != v.rbegin() + b; itr++){
                mine.push_back(*itr);
            }

            sort(mine.begin(), mine.end(), greater<int>{});
            int rest_k = k - a - b;
            while( !mine.empty() && rest_k != 0 && mine.back() <= 0){
                mine.pop_back();
                rest_k--;
            }
            
            int mine_sum = 0;
            for(auto& x : mine){
                mine_sum += x;
            }
            ans = max(ans, mine_sum);
        }
    }

    cout << ans << endl;
    return 0;
}

E問題(未AC)

まだ解いておりません。

F問題(未AC)

まだ解いておりません。