---
# System prepended metadata

title: 競プロ班講義第六回 演習問題解説

---

# 競プロ班講義第六回 演習問題解説

### [B - How many?](https://atcoder.jp/contests/abc214/tasks/abc214_b)
a, b, cの値を全探索する。
制約より、S <= 100であるから0 <= a <= 100, 0 <= b <= 100, 0 <= c <= 100の範囲で全探索を行えばよい

#### 実装例
```cpp
#include <iostream> //cout, endl, cin
#include <string> //string, to_string, stoi
#include <vector> //vector
#include <algorithm> //min, max, swap, sort, reverse, lower_bound, upper_bound
#include <utility> //pair, make_pair
#include <tuple> //tuple, make_tuple
#include <map> //map
#include <queue> //queue, priority_queue
#include <set> //set
#include <stack> //stack
#include <deque> //deque
using ll = long long;
using namespace std;

int main() {
    int S, T;
    cin >> S >> T;
    int ans = 0;
    // 0 <= a <= 100, 0 <= b <= 100, 0 <= c <= 100の範囲を全探索
    for (int a = 0; a <= 100; a++) {
        for (int b = 0; b <= 100; b++) {
            for (int c = 0; c <= 100; c++) {
                int sum = a + b + c, product = a * b * c;
                if (sum <= S && product <= T) {
                    ans++; //条件を満たすので答えに1を加算
                }
            }
        }
    }

    cout << ans << endl;
}
```

### [B - Same Name](https://atcoder.jp/contests/abc216/tasks/abc216_b)
ありうる人の組を全て試せばよい。つまり、0 <= i <= N - 1, i+1 <= j <= Nの範囲で全探索を行えばよい

#### 実装例
```cpp
#include <iostream> //cout, endl, cin
#include <string> //string, to_string, stoi
#include <vector> //vector
#include <algorithm> //min, max, swap, sort, reverse, lower_bound, upper_bound
#include <utility> //pair, make_pair
#include <tuple> //tuple, make_tuple
#include <map> //map
#include <queue> //queue, priority_queue
#include <set> //set
#include <stack> //stack
#include <deque> //deque
using ll = long long;
using namespace std;

int main() {
    int N;
    cin >> N;
    vector<string> S(N), T(N);
    for (int i = 0; i < N; i++) cin >> S[i] >> T[i];
    bool ans = false; //同姓同名である人の組が見つかったらtrueにする
    for (int i = 0; i < N; i++) {
        for (int j = i + 1; j < N; j++) {
            if (S[i] == S[j] && T[i] == T[j]) {
                ans = true;
            }
        }
    }
    
    if (ans) {
        cout << "Yes" << endl;
    } else {
        cout << "No" << endl;
    }
}
```

### [B - qwerty](https://atcoder.jp/contests/abc218/tasks/abc218_b)
英小文字で前からi番目(1 <= i <= 26)のものを求めることができればよい。

英小文字で前からi番目(1 <= i <= 26)のものは次のように求めることができる。（英大文字についても同様に求められる。）
```cpp
('a' + i - 1)

cout << (char)('a' + 0) << endl; // a
cout << (char)('a' + 5) << endl; // f
cout << (char)('A' + 1) << endl; // B
cout << ('a' + 5) << endl; // 102
```
これは'a'、'A'、'@'などの各文字が内部では特定の数字に対応付けられて扱われていることを利用している。
各文字がどの数字に対応しているかは[ASCII、10 進数、16 進数、8 進数、およびバイナリーの変換表](https://www.ibm.com/docs/ja/aix/7.1?topic=adapters-ascii-decimal-hexadecimal-octal-binary-conversion-table)の10進数の欄を見るとよい。
なお、c++の仕様でchar型とint型の演算を行うと暗黙の型変換が行われint型になることに注意

#### 実装例
```cpp
#include <iostream> //cout, endl, cin
#include <string> //string, to_string, stoi
#include <vector> //vector
#include <algorithm> //min, max, swap, sort, reverse, lower_bound, upper_bound
#include <utility> //pair, make_pair
#include <tuple> //tuple, make_tuple
#include <map> //map
#include <queue> //queue, priority_queue
#include <set> //set
#include <stack> //stack
#include <deque> //deque
using ll = long long;
using namespace std;

int main() {
    vector<int> P(26);
    for (int i = 0; i < 26; i++) cin >> P[i];
    string ans; // string ans = "" と同じ
    
    for (int i = 0; i < 26; i++) {
        // 文字列の結合
        ans += (char)('a' + P[i] - 1); //英小文字で前からP_i番目(1<= P[i] <= 26)のものを求める
    }
    cout << ans << endl;
}
```

### [B - String Shifting](https://atcoder.jp/contests/abc223/tasks/abc223_b)
Nを文字列Sの長さとすると、Sに右シフトを1回行ったものとSに左シフトをN-1回行ったものは同じものであるから、操作として右シフトのみ考えればよい。
また、Sに右シフトをN回行ったものはSに等しくなるため、右シフトを行う回数はN-1回でよい。

#### 実装例
```cpp
#include <iostream> //cout, endl, cin
#include <string> //string, to_string, stoi
#include <vector> //vector
#include <algorithm> //min, max, swap, sort, reverse, lower_bound, upper_bound
#include <utility> //pair, make_pair
#include <tuple> //tuple, make_tuple
#include <map> //map
#include <queue> //queue, priority_queue
#include <set> //set
#include <stack> //stack
#include <deque> //deque
using ll = long long;
using namespace std;

int main() {
    string S;
    cin >> S;
    int N = S.size();
    vector<string> T(N, S);
    for (int i = 1; i < N; i++) {
        T[i][0] = T[i - 1][N - 1];
        for (int j = 0; j < N - 1; j++) T[i][j + 1] = T[i - 1][j];
    }
    sort(T.begin(), T.end());
    cout << T[0] << endl;
    cout << T[N - 1] << endl;
}
```

### [B - Mongeness](https://atcoder.jp/contests/abc224/tasks/abc224_b)
問題文の通りに、1 <= i_1 < i_2 <= H および 1 <= j_1 < j_2 <= W を満たす全ての整数の組について条件が成り立つかどうか判定すればよい

#### 実装例
```cpp
#include <iostream> //cout, endl, cin
#include <string> //string, to_string, stoi
#include <vector> //vector
#include <algorithm> //min, max, swap, sort, reverse, lower_bound, upper_bound
#include <utility> //pair, make_pair
#include <tuple> //tuple, make_tuple
#include <map> //map
#include <queue> //queue, priority_queue
#include <set> //set
#include <stack> //stack
#include <deque> //deque
using ll = long long;
using namespace std;

int main() {
    int H, W;
    cin >> H >> W;
    vector<vector<int>> A(H, vector<int>(W));
    for (int i = 0; i < H; i++) {
        for (int j = 0; j < W; j++) {
            cin >> A[i][j];
        }
    }

    bool ans = true;
    for (int i1 = 0; i1 < H - 1; i1++) {
        for (int i2 = i1 + 1; i2 < H; i2++) {
            for (int j1 = 0; j1 < W - 1; j1++) {
                for (int j2 = j1 + 1; j2 < W; j2++) {
                    if (A[i1][j1] + A[i2][j2] > A[i2][j1] + A[i1][j2]) ans = false;
                }
            }
        }
    }

    if (ans) {
        cout << "Yes" << endl;
    } else {
        cout << "No" << endl;
    }
}
```

### [B - Counting Arrays](https://atcoder.jp/contests/abc226/tasks/abc226_b)
N個の数列$A_i$ (1 <= i <= N)からなるsetを作れば、そのsetのサイズが答えとなる。

#### 実装例
```cpp
#include <iostream> //cout, endl, cin
#include <string> //string, to_string, stoi
#include <vector> //vector
#include <algorithm> //min, max, swap, sort, reverse, lower_bound, upper_bound
#include <utility> //pair, make_pair
#include <tuple> //tuple, make_tuple
#include <map> //map
#include <queue> //queue, priority_queue
#include <set> //set
#include <stack> //stack
#include <deque> //deque
using ll = long long;
using namespace std;

int main() {
    int N;
    cin >> N;
    vector<int> L(N);
    vector<vector<int>> A(N);
    set<vector<int>> se;
    for (int i = 0; i < N; i++) {
        cin >> L[i];
        for (int j = 0; j < L[i]; j++) {
            int a;
            cin >> a;
            A[i].push_back(a);
        }

        se.insert(A[i]);
    }
    
    cout << se.size() << endl;
}
```

### [B - Triple Metre](https://atcoder.jp/contests/abc230/tasks/abc230_b)
各i(1 <= i <= 3*$10^5$)について、Tのi文字目からのN文字とSが一致するか調べればよい

#### 実装例
```cpp
#include <iostream> //cout, endl, cin
#include <string> //string, to_string, stoi
#include <vector> //vector
#include <algorithm> //min, max, swap, sort, reverse, lower_bound, upper_bound
#include <utility> //pair, make_pair
#include <tuple> //tuple, make_tuple
#include <map> //map
#include <queue> //queue, priority_queue
#include <set> //set
#include <stack> //stack
#include <deque> //deque
using ll = long long;
using namespace std;

int main() {
    string S;
    cin >> S;
    int N = S.size();

    string T;
    // oxxを10^5個連結する
    for (int i = 0; i < 100000; i++) {
        T += "oxx";
    }

    bool ans = false;
    for (int i = 0; i < 300000; i++) {
        // Sのi文字目からのN文字とSが一致するか調べる
        if (i+N >= 300000) continue;
        if (T.substr(i, N) == S) {
            ans = true;
        }
    }

    if (ans) {
        cout << "Yes" << endl;
    } else {
        cout << "No" << endl;
    }
}
```

### [B - Election](https://atcoder.jp/contests/abc231/tasks/abc231_b)


#### 実装例
```cpp
#include <iostream> //cout, endl, cin
#include <string> //string, to_string, stoi
#include <vector> //vector
#include <algorithm> //min, max, swap, sort, reverse, lower_bound, upper_bound
#include <utility> //pair, make_pair
#include <tuple> //tuple, make_tuple
#include <map> //map
#include <queue> //queue, priority_queue
#include <set> //set
#include <stack> //stack
#include <deque> //deque
using ll = long long;
using namespace std;

int main() {
    int N;
    cin >> N;
    vector<string> S(N);
    for (int i = 0; i < N; i++) {
        cin >> S[i];
    }

    map<string, int> mp;
    for (int i = 0; i < N; i++) {
        mp[S[i]]++;
    }
    int mx = 0;
    string ans;
    for (auto it = mp.begin(); it != mp.end(); it++) {
        if (it->second > mx) {
            ans = it->first;
            mx = it->second;
        }
    }

    cout << ans << endl;
}
```

