LoginSignup
1
0

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?

More than 3 years have passed since last update.

@hyasuda(Hiromasa Yasuda)

AtCoder ABC188 C++ 解答まとめ

Last updated at Posted at 2021-01-13

このページの趣旨

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

C問題

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

解法その１

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

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になるまで繰り返すと、決勝戦のプレイヤーのレートのみを含み、最後にその２つのプレイヤーのレートの最小値を取ることで準優勝のプレイヤーを特定することができる。

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;
}

解法その３

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

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を左または右にシフトする演算子であり、

<<
または
>>

で記述する。

以下、サンプルコード。

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関数 を使ったほうが良いと個人的には思う。

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

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

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

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型を定義することが可能。

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型変数を使ったいもす方法）

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型を使った方法）

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

拡張for文

配列のすべての要素を計算する際に使う。
参考4

mapの初期化について

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

vector::emplace_back について

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型のときと同じではないことは認識しておいたほうが良いかもしれない。

  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 ↩

  3. https://imoz.jp/algorithms/imos_method.html ↩

  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 ↩

1
0
0

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
Sign upLogin
1
0

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?