【ABC235】B - Climbing Takahashi，C - The Kth Time QueryをC++で解説

#はじめに
　皆さんこんにちは！ C++で競プロ問題の解説をします！今回は **ABC235 B, C** です！

 少しでも役に立ったら**LGTM**して頂けるとうれしいです！
 
わからないことなどあれば下の**コメント**や[Twitter](https://twitter.com/python05238919)からお願いいたします!

####問題概要
 左端の台に立っており，以下の条件で右の台に移動する．
　・今立っている台が右端ではなく，右隣の台の高さが今立っている台の高さより高い．
　この時での最後に立っている台の高さを求めよ．
####制約
　・$2 \leq N \leq 10^5$
　・$1 \leq H_i \leq 10^9$
　・入力はすべて整数．
##考察
####ポイント
 **ループと分岐を使おう！**
####解説
 条件通りに台の高さを見ていき，
　**右隣の台が今の高さより大きいとき**台の値を更新します．
　**右隣の台が今の高さ以下のとき**それ以降は移動しないのでその台が答えとなります．

　それでは実装していきましょう！
##実装
　`for`で順番に見ていきます．解説通りに更新し，**右隣の台が今の高さ以下のとき**は`break`でループを終わらせます．

##正解コード

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

int main()
{

    int N;
    //問題の初期値
    long long ans = -1;

    //入力
    cin >> N;

    //条件を見ていく．
    for(int i = 0; i < N; i++){
        long long h;
        cin >> h;
        if(h > ans) ans = h;
        else{
            break;
        }
    }

    //出力
    cout << ans << endl;
}
```

#[C - The Kth Time Query](https://atcoder.jp/contests/abc235/tasks/abc235_c)
####問題概要
 長さ$N$の数列$A = (a_1, ... , a_N)$での以下の$Q$個のクエリを答えよ．
・クエリ$i$:整数の組$(x_i, k)$が与えられたときの数$x_i$が$k_i$回目に登場するのは数列の何番目なのか？
条件を満たさない場合は$-1$を出力しなさい．

####制約
・$1 \leq N, Q \leq 2 × 10^5$
・$0 \leq a_i\leq 10^9 (1 \leq i \leq N))$
・$0 \leq x_ i, k_i \leq 10^9 (1 \leq i \leq Q)$
##考察
####ポイント
 **mapを使おう！**
####解説
 C問題なので計算量を減らすことを考えましょう．配列で数列を見ようとするとクエリごとに最大で$O(N)$かかってしまい，全体の計算量が$O((Q+N)N)$となり，間に合いません．
　ここで**mapを使うことにより毎回のクエリで$O(logN)$で答えが得る**ことができます．これにより，全体の計算量は$O((Q+N)logN)$となり時間内に間に合います．

それでは実装していきましょう！
##実装
 **map**の宣言を`map<long long, vector<int>>`にすることにより，数列の値が何番目なのか`push_back`することができます．
　また$-1$となる条件は$x_i$の`map`の大きさが$0$もしくはそれ以上のときです．
##正解コード

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

int main()
{
    //入力
    int N, Q;
    cin >> N >> Q;
    //mapの宣言
    map<long long, vector<int>> mp;

    for (int i = 0; i < N; i++)
    {
        long long a;
        cin >> a;
        //何番目なのかを加える．
        mp[a].push_back(i+1);    
    }

    for (int q = 0; q < Q; q++)
    {
        long long x, k;
        cin >> x >> k;

        //-1の条件を判定し出力
        if(mp[x].size() < k) cout << -1 << "\n";
        else{
            cout << mp[x][k-1] << "\n"; 
        }
    }
}

```

#最後に
　私自身は今回のコンテストで違う解き方で解いたのですが，遠回りでややこしいのでソースコードのみ記載します．
流れは
・数列と何番目なのかを`pair`で保持，また値があるかは`set`にいれる．
・ソートして$x$から$k$番目の値が$x$ときと，`set`にない場合は$-1$を出力．
・それ以外は`pair`から出力.

<details><summary>私の解答</summary><div>

```C++
#include <bits/stdc++.h>
using namespace std;

int main()
{
    int N, Q;
    cin >> N >> Q;
    set<long long> st;
    vector<long long> a(N);
    vector<pair<long long, int>> ans(N);
    for(int i = 0; i < N; i++){
        cin >> a[i];
        ans[i] = make_pair(a[i], i+1);
        st.insert(a[i]);
    }
    //ソートして二分探索できるようにする．
    sort(ans.begin(), ans.end());
    sort(a.begin(), a.end());

    for(int q = 0; q < Q; q++){
        long long x, k;
        cin >> x >> k;
        //二分探索してxの値をみる．
        auto iter = lower_bound(a.begin(), a.end(), x);
        int b = iter - a.begin();
        //-1かの判定
        if(st.count(x) == 0 || b + k - 1 >= N||ans[b + k-1].first != x) cout << -1 << endl;
        else{
            cout << ans[b + k-1].second << endl;
        }
    }
}

```　
</div></details>