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

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

### コンテストURL
https://atcoder.jp/contests/abc354

### 開催日
2024/05/18 21:00-22:40

---

## [A: Exponential Plant](https://atcoder.jp/contests/abc354/tasks/abc354_a)
**解法**
- 問題文通りにシミュレーションする
```cpp: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](https://atcoder.jp/contests/abc354/tasks/abc354_b)
**解法**
- `sort()` で文字列を辞書順にソートできる
```cpp: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](https://atcoder.jp/contests/abc354/tasks/abc354_c)
**解法**
- カードの強さ $A_i$ の降順にソートしてこれまでの最小コストと比較する
    - これまでの最小コストより大きければ当該カードを捨てる
    - これまでの最小コスト以下であれば当該カードは捨てずに残し、最小コストを更新する
    - カードの強さ $A_i$ 、コスト $C_i$ 、カードの番号 $i$ を `vector<tuple<int, int, int>>` で管理する
```cpp: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](https://atcoder.jp/contests/abc354/tasks/abc354_d)
**解法**
- 負の座標の処理を避けるために $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` と同じ意味になってしまう
```cpp: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;
}
```