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

はじめに

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

少しでも役に立ったらLGTMして頂けるとうれしいです！

わからないことなどあれば下のコメントやTwitterからお願いいたします!

問題概要

左端の台に立っており，以下の条件で右の台に移動する．
　・今立っている台が右端ではなく，右隣の台の高さが今立っている台の高さより高い．
　この時での最後に立っている台の高さを求めよ．

制約

　・$2 \leq N \leq 10^5$
　・$1 \leq H_i \leq 10^9$
　・入力はすべて整数．

考察

ポイント

ループと分岐を使おう！

解説

条件通りに台の高さを見ていき，
　右隣の台が今の高さより大きいとき台の値を更新します．
　右隣の台が今の高さ以下のときそれ以降は移動しないのでその台が答えとなります．

　それでは実装していきましょう！

実装

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

正解コード

# 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

問題概要

長さ$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$もしくはそれ以上のときです．

正解コード

# 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から出力.

私の解答

# 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>