【ABC345】AtCoder Beginner Contest 345【C++】

### コンテスト名
モノグサプログラミングコンテスト2024（AtCoder Beginner Contest 345）

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

### 開催日
2024/03/16 21:00-22:40

---

## [A: Leftrightarrow](https://atcoder.jp/contests/abc345/tasks/abc345_a)
**解法**
- 条件を満たすかそれぞれ確かめる
  1. 1 文字目は `<`
  2. `S.size()` 文字目は `>`
  3. ほかはすべて `=`

```cpp:ABC345A.cpp
#include <iostream>
#include <string>
using namespace std;

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

    if(s[0]!='<'){
        cout << "No" << endl;
        return 0;
    }
    if(s.back()!='>'){
        cout << "No" << endl;
        return 0;
    }
    for(int i=1; i<s.size()-1; i++){
        if(s[i]!='='){
            cout << "No" << endl;
            return 0;
        }
    }

    cout << "Yes" << endl;
    return 0;
}
```

## [B: Integer Division Returns](https://atcoder.jp/contests/abc345/tasks/abc345_b)
**解法**
- $a \geqq 0, b > 0$ のとき $\left\lceil\frac{a}{b}\right\rceil = \left\lfloor\frac{a + b - 1}{b}\right\rfloor$
- C++ の整数除算は正でも負でも小数点以下を切り捨てる
- $X$ が負のときはそのまま出力

```cpp:ABC345B.cpp
#include <iostream>
using namespace std;

int main(){
    long long int x;
    cin >> x;

    if(x>=0){
        cout << (x + (10-1))/10 << endl;
    }else{
        cout << x/10 << endl;
    }

    return 0;
}
```

## [C: One Time Swap](https://atcoder.jp/contests/abc345/tasks/abc345_c)
**解法**
- 文字列 $S$ において $i$ 文字目と $j$ 文字目が異なる整数の組 $(i, j)$ の個数を求める
- $1 \leqq i < j \leqq N$ を満たす整数の組 $(i, j)$ は ${}_N \mathrm{C}_2$ 通り
- $i$ 文字目と $j$ 文字目が同じときは入れ替えても元の文字列 $S$ と変わらない
- 文字 `x` が文字列 $S$ に $2 \leqq k \leqq N$ 個含まれているとき `x` 同士を入れ替えてできる元の文字列 $S$ と変わらない文字列は ${}_k \mathrm{C}_2$ 通り
- 各文字の個数を `unordered_map<char, long long int>` で管理して元の文字列 $S$ と変わらない場合を引く
- 「元の文字列 $S$ と変わらない場合」も 1 通りと数えるため `+1` する

```cpp:ABC345C.cpp
#include <iostream>
#include <string>
#include <unordered_map>
using namespace std;

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

    unordered_map<char, long long int> M;
    bool same = false;
    long long int n = s.size();
    for(int i=0; i<n; i++){
        M[s[i]]++;
        if(M[s[i]]>1){
            same = true;
        }
    }

    long long int sum = (n*(n-1))/2;
    long long int cnt = 0;
    for(unordered_map<char, long long int>::iterator it=M.begin(); it!=M.end(); it++){
        pair<char, long long int> item = *it;
        if((item.second*(item.second-1))/2){
            cnt += (item.second*(item.second-1))/2;
        }
    }

    if(same){
        cout << sum - cnt + 1 << endl;
    }else{
        cout << sum << endl;
    }
    
    return 0;
}
```

## [D: Tiling](https://atcoder.jp/contests/abc345/tasks/abc345_d)
**解法**
- 全探索
  1. 順列全探索 + bit 全探索 + マス目全探索
  2. 深さ優先探索 (DFS)
- 左上からタイルを敷き詰めて全マス埋まれば `Yes`
- 標準エラー出力 `cerr << endl` でどのように埋まったか確認できる
1. 順列全探索 + bit 全探索 + マス目全探索
    - タイルを並べる順番を順列全探索
    - タイルの向きを bit 全探索
    - 「使用されないタイル」は順列の後ろのほうにあると考える
    - 順列の最後のタイルまで使用する場合（ $N$ 枚すべて利用する場合）の判定場所に注意
    - 空いているマスの座標を代入する変数を `-1` などで初期化しておくと判定が楽
2. 深さ優先探索 (DFS)
    - `vector<int>` で使用したタイルを記録する
    - `for` と `swap` で向きを探索

```cpp:ABC345D_1.cpp
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main(){
    int n, h, w;
    cin >> n >> h >> w;

    vector<int> A(n), B(n);
    for(int i=0; i<n; i++){
        cin >> A[i] >> B[i];
    }

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

    do{
        for(int i=0; i<(1<<n); i++){
            vector<vector<int>> M(h, vector<int>(w));
            for(int j=0; j<n; j++){
                int check = (i & (1<<j));
                int a, b;
                if(check){
                    a = A[P[j]];
                    b = B[P[j]];
                }else{
                    a = B[P[j]];
                    b = A[P[j]];
                }

                int nh = -1, nw = -1;
                for(int k=0; k<h; k++){
                    for(int l=0; l<w; l++){
                        if(!M[k][l] && nh==-1){
                            nh = k;
                            nw = l;
                        }
                    }
                }

                if(nh+a>h || nw+b>w){
                    break;
                }
                
                bool flag = true;
                for(int k=0; k<a; k++){
                    for(int l=0; l<b; l++){
                        if(M[nh+k][nw+l]){
                            flag = false;
                        }
                        M[nh+k][nw+l] = P[j] + 1;
                    }
                }

                if(!flag){
                    break;
                }

                flag = true;
                for(int k=0; k<h; k++){
                    for(int l=0; l<w; l++){
                        if(!M[k][l]){
                            flag = false;
                        }
                    }
                }
                if(flag){
                    cout << "Yes" << endl;
                    for(int k=0; k<h; k++){
                        for(int l=0; l<w; l++){
                            cerr << M[k][l];
                        }
                        cerr << endl;
                    }
                    return 0;
                }
            }
        }
    }while(next_permutation(P.begin(), P.end()));

    cout << "No" << endl;
    return 0;
}
```

```cpp:ABC345D_2.cpp
#include <iostream>
#include <vector>
using namespace std;

int n, h, w;
vector<int> A, B;

bool dfs(vector<vector<int>> &M, vector<int> &used){
    int ni = -1, nj = -1;
    for(int i=0; i<h; i++){
        for(int j=0; j<w; j++){
            if(!M[i][j] && ni==-1){
                ni = i;
                nj = j;
            }
        }
    }

    if(ni==-1){
        for(int k=0; k<h; k++){
            for(int l=0; l<w; l++){
                cerr << M[k][l];
            }
            cerr << endl;
        }
        return true;
    }

    for(int i=0; i<n; i++){
        if(used[i]){
            continue;
        }
        int a = A[i], b = B[i];
        for(int j=0; j<2; j++){
            swap(a, b);
            if(ni+a>h || nj+b>w){
                continue;
            }

            bool flag = true;
            vector<vector<int>> Ms = M;
            vector<int> useds = used;
            for(int k=0; k<a; k++){
                for(int l=0; l<b; l++){
                    if(Ms[ni+k][nj+l]){
                        flag = false;
                    }
                    Ms[ni+k][nj+l] = i + 1;
                }
            }
            if(!flag){
                continue;
            }
            useds[i] = 1;
            if(dfs(Ms, useds)){
                return true;
            }
        }
    }

    return false;
}

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

    A.resize(n);
    B.resize(n);
    for(int i=0; i<n; i++){
        cin >> A[i] >> B[i];
    }

    vector<vector<int>> M(h, vector<int>(w, 0));
    vector<int> used(n, 0);
    if(dfs(M, used)){
        cout << "Yes" << endl;
    }else{
        cout << "No" << endl;
    }

    return 0;
}
```