【ABC354】AtCoder Beginner Contest 354【C++】

コンテスト名

パナソニックグループ プログラミングコンテスト2024（AtCoder Beginner Contest 354）

コンテストURL

開催日

2024/05/18 21:00-22:40

---

A: Exponential Plant

解法

• 問題文通りにシミュレーションする

ABC354A.cpp

#include <iostream>
using namespace std;

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

    int day = 0, height = 0;
    while(height<=h){
        height += (1<<day);
        day++;
    }

    cout << day << endl;
    return 0;
}

B: AtCoder Janken 2

解法

• sort() で文字列を辞書順にソートできる

ABC354B.cpp

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

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

    string s;
    int c, t = 0;
    vector<string> V;
    for(int i=0; i<n; i++){
        cin >> s >> c;
        t += c;
        V.push_back(s);
    }

    sort(V.begin(), V.end());

    cout << V[t%n] << endl;
    return 0;
}

C: AtCoder Magics

解法

• カードの強さ $A_i$ の降順にソートしてこれまでの最小コストと比較する
  • これまでの最小コストより大きければ当該カードを捨てる
  • これまでの最小コスト以下であれば当該カードは捨てずに残し、最小コストを更新する
  • カードの強さ $A_i$ 、コスト $C_i$ 、カードの番号 $i$ を vector<tuple<int, int, int>> で管理する

ABC354C.cpp

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

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

    vector<tuple<int, int, int>> V;
    int a, c;
    for(int i=0; i<n; i++){
        cin >> a >> c;
        V.emplace_back(a, c, i+1);
    }

    sort(V.rbegin(), V.rend());

    auto [a0, c0, id] = V[0];
    int minc = c0;
    vector<int> V2;
    V2.push_back(id);
    for(int i=1; i<V.size(); i++){
        auto [a, c, id] = V[i];
        if(c<=minc){
            V2.push_back(id);
            minc = min(minc, c);
        }
    }

    sort(V2.begin(), V2.end());

    cout << V2.size() << endl;
    for(int i=0; i<V2.size(); i++){
        if(i){
            cout << " ";
        }
        cout << V2[i];
    }

    cout << endl;
    return 0;
}

D: AtCoder Wallpaper

解法

• 負の座標の処理を避けるために $A, B, C, D$ に $10^9$ を足す
• $(0, 0)$ を左下の頂点として考えて包除原理で答えを求める
  • $f(C, D) - f(A, D) - f(C, B) + f(A, B)$
• $2 \times 4$ の長方形が繰り返されていることに着目して面積を求める
• 計算の順序に注意する
  • long long int res = (x/4) * (y/2) * 8; では、割り算の切り捨てを行ってから掛け算をするように括弧で囲む
  • x/4 * y/2 * 8 にすると、(x/4 * y)/2 * 8 と同じ意味になってしまう

ABC354D.cpp

#include <iostream>
using namespace std;

long long int f(long long int x, long long int y){
    long long int res = (x/4) * (y/2) * 8;

    if(y%2==1){
        res += (x/4) * 4;

        if(x%4==1){
            res += 2;
        }else if(x%4==2){
            res += 3;
        }else if(x%4==3){
            res += 3;
        }
    }

    if(x%4==1){
        res += (y/2) * 3;
    }else if(x%4==2){
        res += (y/2) * 6;
    }else if(x%4==3){
        res += (y/2) * 7;
    }

    return res;
}

int main(){
    long long int a, b, c, d;
    cin >> a >> b >> c >> d;

    a += 1e9;
    b += 1e9;
    c += 1e9;
    d += 1e9;

    long long int ans = f(c, d) - f(a, d) - f(c, b) + f(a, b);
    cout << ans << endl;
    return 0;
}