AtCoder ABC188 C++ 解答まとめ

## このページの趣旨

AtCoderのABC問題について、問題の解法についてまとめたもの。
まだまだ未熟者なので、他の解法があれば知りたいのでコメントで共有していただけると嬉しいです。
A問題とB問題については省略します。
（当面はC問題とD問題について解説する予定）

## C問題

問題ページ
https://atcoder.jp/contests/abc188/tasks/abc188_c

### 解法その１
先頭２つ取り出してmaxの値を後ろにつめる手法。
queue型を使うことで、先頭２つを比較し、queue型の変数の後ろにつめることができる。
比較する際のmax/min値を取り出すことで、queue型変数のsizeが1になったときの最小値が準優勝したプレイヤーのレートになる。
あとは、そのレートに対応するプレイヤー番号をmap型の変数で取り出せばよい。

```cpp:c_01.cpp
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0 ; i < (n) ; ++i)

int main(){
    int n;
    cin >> n;
    int n2 = 1 << n;
    vector<int> a(n2);
    rep(i, n2) cin >> a[i];
    map<int, int> mp;
    rep(i, n2) mp[a[i]] = i+1;
    queue<int> q;
    rep(i, n2) q.push(a[i]);
    int val_max, val_min;
    while( q.size() > 1 ){
        int val1 = q.front(); q.pop();
        int val2 = q.front(); q.pop();
        val_min = min(val1, val2);
        val_max = max(val1, val2);
        q.push( val_max );
    }
    int ans = val_min;
    cout << mp[ans] << endl;
}
```

### 解法その２
先頭２つずつを取り出していって、それぞれのペアの最大値だけを取り出す。最終的に二個になるまでループする。
おそらく解法としてはもっとも単純なもの。
２こずつ比較したmax値のみをつめこんだvectorともともとのvector変数をswapして、vectorサイズが2になるまで繰り返すと、決勝戦のプレイヤーのレートのみを含み、最後にその２つのプレイヤーのレートの最小値を取ることで準優勝のプレイヤーを特定することができる。

```cpp:c_02.cpp
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0 ; i < (n) ; ++i)
using ll = long long;
using P = pair<int, int>;


int main(){

    int n;
    cin >> n;
    int n2 = 1 << n;
    vector<int> a(n2);
    rep(i, n2) cin >> a[i];
    map<int, int> mp;
    rep(i, n2) mp[a[i]] = i+1;
    while( a.size() > 2 ){
        vector<int> na;
        for( int i = 0 ; i < a.size() ; i+=2 ){
            na.push_back( max(a[i], a[i+1]) );
        }
        swap(a, na);
    }
    int ans = min(a[0], a[1]);
    // cout << ans << endl;
    cout << mp[ans] << endl;
}
```


### 解法その３

前半と後半それぞれの最大値を取り出して、低い方だけを取り出す。
全プレイヤーのレートを中間で前後で分けて、それぞれの最大値を取り出す。
それが決勝のカードになるので、その２つのカードの最小値が準優勝したプレイヤーのレートになる。

```cpp:c_03.cpp
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0 ; i < (n) ; ++i)
using ll = long long;
using P = pair<int, int>;


int main(){

    int n;
    cin >> n;
    int n2 = 1 << n;
    vector<int> a(n2);
    rep(i, n2) cin >> a[i];
    map<int, int> mp;
    rep(i, n2) mp[a[i]] = i+1;

    int max1 = 0; int max2 = 0;
    for( int i = 0 ; i < n2/2 ; i++ ){
        max1 = max( a[i]   , max1 );
        max2 = max( a[n2-i-1], max2 );
    }
    int ans = min(max1, max2);
    cout << mp[ans] << endl;
}
```


### Point

#### シフト演算子

シフト演算子２進数表示した際のbitを左または右にシフトする演算子であり、

```
<<
または
>>
```

で記述する。

以下、サンプルコード。

```cpp:shift_sample.cpp
#include <bits/stdc++.h>
using namespace std;

int main(){
    int a = 1;
    int b = 1 << 1;
    int c = 1 << 2;
    int d = 1 << 3;
    cout << "Definition" << "\t" << "10 bit" << "\t" << "2bit"        << endl;
    cout << "a = 1     " << "\t" << a        << "\t" << bitset<10>(a) << endl;
    cout << "b = 1 << 1" << "\t" << b        << "\t" << bitset<10>(b) << endl;
    cout << "c = 1 << 2" << "\t" << c        << "\t" << bitset<10>(c) << endl;
    cout << "d = 1 << 3" << "\t" << d        << "\t" << bitset<10>(d) << endl;
}
```

これを実行すると以下のような出力が得られる。

```:Output
Definition      10 bit  2bit
a = 1           1       0000000001
b = 1 << 1      2       0000000010
c = 1 << 2      4       0000000100
d = 1 << 3      8       0000001000
```

この出力を見るとわかるように、シフト演算子"<<"を使うことで、2進数表示のビットを左にシフトしていることがわかる。
このC問題では、問題に「2^N 人でトーナメント」とあるので、上記の手法を使うことで２の冪乗（べき乗）を簡単に得ることができる。

ちなみに、視認性がよいという意味では、以下のように pow関数 を使ったほうが良いと個人的には思う。

```cpp:pow_sample.cpp
#include <bits/stdc++.h>
using namespace std;

int main(){

    int a = pow(2, 1);
    int b = pow(2, 2);
    int c = pow(2, 3);

    cout << "Definition    " << "\t" << "value"  << endl;
    cout << "a = pow(2, 1) " << "\t" << a        << endl;
    cout << "b = pow(2, 2) " << "\t" << b        << endl;
    cout << "c = pow(2, 3) " << "\t" << c        << endl;

}

```

出力は以下のようになる。

```:Output
Definition      value
a = pow(2, 1)   2
b = pow(2, 2)   4
c = pow(2, 3)   8
```


#### map型

"map はユニークな要素を格納する連想コンテナの一種であり、キーとそれに対応する値を格納する。"[^1]
[^1]: cpprefjp - C++日本語リファレンス https://cpprefjp.github.io/reference/map/map.html
連想配列や辞書と呼ばれるデータ構造である。[^2]
[^2]: AtCoder C++入門 AtCoder Programming Guide for beginners (APG4b) https://atcoder.jp/contests/apg4b/tasks/APG4b_aa

このC問題において、回答したいのは、準優勝したプレイヤーの「レート」ではなく、プレイヤーの「番号」なので、「レート」をキーにしてプレイヤー「番号」を取り出すことがmap型を用いることでかのうである。

基本的な使い方は以下のようになる。

```cpp:map_sample.cpp
#include <bits/stdc++.h>
using namespace std;

int main(){
    map<string, int> mp;
    mp.insert(make_pair("c", 30));
    mp.insert(make_pair("a", 10));
    mp.insert(make_pair("b", 20));
    int value = mp.at("a");
    cout << value << endl;
}
```

出力は以下のようになる。

```:Output
10
```

したがって、キー"a"に対応する数値が取り出すことができた。
この問題では、キーを"string型"でなく"int型"で読みこむこともできる。
例えば以下のようにして、map型を定義することが可能。

```cpp:map_sample_02.cpp
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0 ; i < (n) ; ++i)


int main(){
    vector<int> a{3, 4, 2, 5, 1};
    map<int, int> mp;
    rep(i, 5) mp[a[i]] = i+1;
    cout << "key" << "\t" << "value" << endl;
    rep(i, 5) cout << i << "\t" << mp[i+1] << endl;
}
```

ここでは、vector a の値をキーとして、要素順に 1-5 の値を map型の変数 mp に読み込ませいる。
出力は以下のようになる。

```:Output
key     value
0       5
1       3
2       1
3       2
4       4
```

このように、keyとvalueそれぞれint型で紐付いていることがわかる。
結構頻出のテクニックっぽいので、使えるようにしておくと便利そう。


## D問題

問題ページ
https://atcoder.jp/contests/abc188/tasks/abc188_d

### 解法その１（map型変数を使ったいもす方法）

```cpp:d_01.cpp
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0 ; i < (n) ; ++i)
using ll = long long;
using P = pair<int, int>;


int main(){

    int n, C;
    cin >> n >> C;

    map<int, ll> events;
    rep(i, n){
        int a, b, c;
        cin >> a >> b >> c;
        events[a]   += c;
        events[b+1] -= c;
    }
    ll  ans = 0;
    ll  s   = 0;
    int pre = 0;
    for( auto event : events ){
        ans += min<ll>(C, s) * (event.first - pre);
        s   += event.second;
        pre  = event.first;
    }
    cout << ans << endl;
    return 0;
}
```

### 解法その２（map型の代わりにvector型を使った方法）

```cpp:d_02.cpp
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0 ; i < (n) ; ++i)
using ll = long long;
using P = pair<int, int>;
 
 
int main(){
 
    int n, C;
    cin >> n >> C;
 
    // map<int, ll> events;
    vector<P> events;
    rep(i, n){
        int a, b, c;
        cin >> a >> b >> c;
        // events[a]   += c;
        // events[b+1] -= c;
        events.emplace_back(a   , c );
        events.emplace_back(b+1 , -c );
    }
    sort(events.begin(), events.end());
    ll  ans = 0;
    ll  s   = 0;
    int pre = 0;
    for( auto event : events ){
        ans += min<ll>(C, s) * (event.first - pre);
        s   += event.second;
        pre  = event.first;
    }
    cout << ans << endl;
    return 0;
}
```

### Point

#### いもす法

値に変更があるときにだけ計算する方法
参考[^3]
[^3]: https://imoz.jp/algorithms/imos_method.html

#### 拡張for文

配列のすべての要素を計算する際に使う。
参考[^4]
[^4]: https://qiita.com/su_/items/9543a60937d527698b40#:~:text=%E6%8B%A1%E5%BC%B5for%E6%96%87%E3%81%A8%E3%81%AF,%E3%81%AB%E3%83%97%E3%83%AD%E3%82%B0%E3%83%A9%E3%83%A0%E3%81%8C%E6%9B%B8%E3%81%91%E3%81%BE%E3%81%99%E3%80%82

#### mapの初期化について

本来、連想配列において存在しないキーにアクセスするとエラーを吐く。
しかし、C++ の map は存在しないキーにアクセスするとゼロ初期化される。
そのため、いきなり "+=" で値を詰めても大丈夫。

### vector::emplace_back について

```cpp:sample_vector_emplace_back.cpp
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0 ; i < (n) ; ++i)
using ll = long long;
using P = pair<int, int>;


int main(){

    vector<P> v;
    v.emplace_back( 1, 10);
    v.emplace_back( 2, 20);
    v.emplace_back( 3, 30);

    cout << "First : " << endl;
    for( auto a : v ){
        cout << a.first << "\t" << a.second << endl;
    }
    cout << endl;

    v.emplace_back( 1, 5  );
    v.emplace_back( 2, -1 );
    v.emplace_back( 3, 0  );

    cout << "Second : " << endl;
    for( auto a : v ){
        cout << a.first << "\t" << a.second << endl;
    }
    cout << endl;
    
    return 0;
}
```

```:Output
First : 
1       10
2       20
3       30

Second : 
1       10
2       20
3       30
1       5
2       -1
3       0
```

つまり、本来のいもす法とは少し違って、あらかじめ同じキーの値の合計を取っているわけではないが、解法のansの足し合わせの際に結局同じ操作をすることになるので、ここでは問題ない。
ただし、ansを計算する際の計算量はmap型のときと同じではないことは認識しておいたほうが良いかもしれない。